树medium专题

本文最后更新于：2023年2月27日下午

LeetCode95 不同的搜索二叉树2 (yes)

（1）题目：

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

1 2	`输入：n = 3 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]`

1 2	`输入：n = 1 输出：[[1]]`

（2）思路：

定义 generate(start, end) 函数表示当前值的集合为 [start,end]，返回序列 [start,end] 生成的所有可行的二叉搜索树。按照上文的思路，我们考虑枚举 [start,end] 中的值 i 为当前二叉搜索树的根，那么序列划分为了 [start,i−1] 和 [i+1,end] 两部分。我们递归调用这两部分，即 generate(start, i - 1) 和 generate(i + 1, end)，获得所有可行的左子树和可行的右子树，那么最后一步我们只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

（3）代码：

public List<TreeNode> generateTrees(int n) {
    return generate(1, n);
}


public List<TreeNode> generate(int start, int end) {
    List<TreeNode> nodes = new ArrayList<>();
    if (start > end) {
        nodes.add(new TreeNode(0));
        return nodes;
    }

    for (int i = start; i <= end; i++) {
        List<TreeNode> lefts = generate(start, i - 1);
        List<TreeNode> rights = generate(i + 1, end);
        for (TreeNode node : lefts) {
            for (TreeNode treeNode : rights) {
                // 生成root节点时，必须要在内层嵌套循环中生成，如果在外层会导致其引用被覆盖生成相同的子树
                TreeNode root = new TreeNode(i);
                root.left = node.val == 0 ? null : node;
                root.right = treeNode.val == 0 ? null : treeNode;
                nodes.add(root);
            }
        }
    }
    return nodes;
}

LeetCode96 不同的搜索二叉树 (no)

（1）题目：

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

1 2	`输入：n = 3 输出：5`

1 2	`输入：n = 1 输出：1`

（2）思路：

设定dp[n]数组定义：长度为n时存在多少个不同二叉树的种类

状态转义公式：dp[n] = dp[i-1]*dp[n-i], 1<=i<=n

（3）代码：

public int numTrees(int n) {
    int[] dp = new int[n + 1];

    dp[0] = 1;
    dp[1] = 1;
    if (n < 2) {
        return dp[n];
    }
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }

    return dp[n];
}

LeetCode98 验证二叉树 (yes)

（1）题目：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

（2）思路：

自己的解法
- 递归(错误)，只考虑的根节点和左右子树的根节点的大小关系，没考虑和孙子节点的关系
- 中序遍历(正确)，中序遍历二叉搜索树，如何符合则应该是从小到大的排序
官方题解递归的解法
- 设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。
- 那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 helper(root.right, root.val, upper)。
- 函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值。

（3）代码：

// 这个解法错误，没有考虑[5,4,6,null,null,3,7]这种场景
public boolean isValidBST1(TreeNode root) {
    if (root == null) {
        return true;
    }

    return isValidBST1(root.left)
            && isValidBST1(root.right)
            && (null == root.left || root.val > root.left.val)
            && (null == root.right || root.val < root.right.val);
}

// 中序解法
private List<Integer> res = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
    if (null == root) {
        return true;
    }

    boolean left = isValidBST(root.left);
    if (!left) {
        return false;
    }
    if ((res.size() > 0 && res.get(res.size() - 1) >= root.val)) {
        return false;
    } else {
        res.add(root.val);
    }
    boolean right = isValidBST(root.right);
    return right;
}

LeetCode99 恢复二叉树(no)

（1）题目：

给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

1	`输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2]`

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

（2）思路：

先通过先序遍历获取数组，校验数据的排序数

（3）代码：

public void recoverTree(TreeNode root) {
    if (null == root) {
        return;
    }

    List<TreeNode> list = new ArrayList<>();
    goThrough(root, list);
    List<TreeNode> res = new ArrayList<>();
    for (int i = 1; i < list.size(); i++) {
        if (list.get(i - 1).val > list.get(i).val) {
            res.add(list.get(i - 1));
            res.add(list.get(i));
        }
    }
    if (res.size() > 0) {
        int temp = res.get(0).val;
        res.get(0).val = res.get(res.size() - 1).val;
        res.get(res.size() - 1).val = temp;
    }
}
public void goThrough(TreeNode root, List<TreeNode> list) {
    if (root == null) {
        return;
    }

    goThrough(root.left, list);
    list.add(root);
    goThrough(root.right, list);
}

LeetCode102 二叉树的层序遍历

（1）题目：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

（2）思路：

（3）代码：

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    Deque<TreeNode> nodes = new ArrayDeque<>();
    int up = 1;
    int down = 0;
    nodes.addLast(root);
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> level = new ArrayList<>();
    while (!nodes.isEmpty()) {
        TreeNode treeNode = nodes.removeFirst();
        level.add(treeNode.val);
        up--;

        if (null != treeNode.left) {
            nodes.addLast(treeNode.left);
            down++;
        }
        if (null != treeNode.right) {
            nodes.addLast(treeNode.right);
            down++;
        }

        if (up == 0) {
            res.add(level);
            level = new ArrayList<>();
            up = down;
            down = 0;
        }
    }
    return res;
}

LeetCode107 二叉树层序遍历

（1）题目：

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

1	`输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]`

（2）思路：

（3）代码：

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> nodes = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.addLast(root);
    int up = 1;
    int down = 0;
    while (!queue.isEmpty()) {
        TreeNode node = queue.removeFirst();
        list.add(node.val);
        up--;
        if (null != node.left) {
            queue.addLast(node.left);
            down++;
        }
        if (null != node.right) {
            queue.addLast(node.right);
            down++;
        }
        if (0 == up) {
            nodes.add(0, list);
            list = new ArrayList<>();
            up = down;
            down = 0;
        }
    }

    return nodes;
}

LeetCode109 有序链表转为二叉搜索树

（1）题目：

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

1	`输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5]`

（2）思路：

（3）代码：

/**
 * 先转成数组，在组成树
 */
public TreeNode sortedListToBST(ListNode head) {
    if (null == head) {
        return null;
    }
    List<Integer> values = new ArrayList<>();
    while (head != null) {
        values.add(head.val);
        head = head.next;
    }
    
    return sortedArray(values, 0, values.size() - 1);
}

public TreeNode sortedArray(List<Integer> values, int s, int e) {
    if (s > e) {
        return null;
    }
    if (s == e) {
        return new TreeNode(values.get(e));
    }
    if (e - s == 1) {
        TreeNode root = new TreeNode(values.get(s));
        root.right = new TreeNode(values.get(e));
        return root;
    }

    int mid = (e + s) / 2;
    TreeNode root = new TreeNode(values.get(mid));
    root.left = sortedArray(values, s, mid - 1);
    root.right = sortedArray(values, mid + 1, e);
    return root;
}

LeetCode114 二叉树展开为链表

（1）题目：

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

1	`输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]`

（2）思路：

（3）代码：

public void flatten(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    add(root, res);
    TreeNode assembly = assembly(res);
    root.val = assembly.val;
    root.left = null;
    root.right = assembly.right;
}

private TreeNode assembly(List<Integer> res) {
    if (null == res || res.size() == 0) {
        return null;
    }
    TreeNode root = new TreeNode(res.get(0));
    TreeNode index = root;
    for (int i = 1; i < res.size(); i++) {
        index.right = new TreeNode(res.get(i));
        index = index.right;
    }
    return root;
}


private void add(TreeNode root, List<Integer> res) {
    if (null == root) {
        return;
    }

    res.add(root.val);
    add(root.left, res);
    add(root.right, res);
}

/**
 * 官方题解，可以一边遍历一边赋值
 */
public void flatten1(TreeNode root) {
    if (root == null) {
        return;
    }
    Deque<TreeNode> stack = new LinkedList<TreeNode>();
    stack.push(root);
    TreeNode prev = null;
    while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        if (prev != null) {
            prev.left = null;
            prev.right = curr;
        }
        TreeNode left = curr.left, right = curr.right;
        if (right != null) {
            stack.push(right);
        }
        if (left != null) {
            stack.push(left);
        }
        prev = curr;
    }
}

/**
 * 非递归先序遍历
 */
public List<Integer> rlr(TreeNode root) {
    if (null == root) {
        return new ArrayList<>();
    }

    Deque<TreeNode> nodes = new ArrayDeque<>();
    nodes.addLast(root);
    List<Integer> res = new ArrayList<>();
    while (!nodes.isEmpty()) {
        TreeNode treeNode = nodes.removeLast();
        res.add(treeNode.val);
        if (null != treeNode.right) {
            nodes.addLast(treeNode.right);
        }
        if (null != treeNode.left) {
            nodes.addLast(treeNode.left);
        }
    }
    return res;
}

LeetCode116 填充每个节点的下一个右侧节点指针(no)

（1）题目：

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

（2）思路：

利用队列来实现，需要额外的队列空间
优化思路：每一层都相当于是一个链表，不用放在队列而直接遍历上一层链表

（3）代码：

public Node connect(Node root) {
    if (root == null) {
        return root;
    }
    Deque<Node> deque = new LinkedList<>();
    deque.addLast(root);
    int up = 1;
    int down = 0;
    Node last = null;
    while (!deque.isEmpty()) {
        Node node = deque.removeFirst();
        up--;

        if (last == null) {
            last = node;
        } else {
            last.next = node;
            last = last.next;
        }

        if (node.left != null) {
            deque.addLast(node.left);
            down++;
        }
        if (node.right != null) {
            deque.addLast(node.right);
            down++;
        }
        if (up == 0) {
            up = down;
            down = 0;
            node.next = null;
            last = null;
        }
    }
    return root;
}

// 优化思路
public Node connect2(Node root) {
        if (root == null)
            return root;
        //cur我们可以把它看做是每一层的链表
        Node cur = root;
        while (cur != null) {
            //遍历当前层的时候，为了方便操作在下一
            //层前面添加一个哑结点（注意这里是访问
            //当前层的节点，然后把下一层的节点串起来）
            Node dummy = new Node(0);
            //pre表示访下一层节点的前一个节点
            Node pre = dummy;
            //然后开始遍历当前层的链表
            while (cur != null) {
                if (cur.left != null) {
                    //如果当前节点的左子节点不为空，就让pre节点
                    //的next指向他，也就是把它串起来
                    pre.next = cur.left;
                    //然后再更新pre
                    pre = pre.next;
                }
                //同理参照左子树
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                //继续访问这一行的下一个节点
                cur = cur.next;
            }
            //把下一层串联成一个链表之后，让他赋值给cur，
            //后续继续循环，直到cur为空为止
            cur = dummy.next;
        }
        return root;
    }

LeetCode129 根节点到叶节点之和

（1）题目：

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

（2）思路：

先存入队列中，然后到叶子节点则计算当前路径的值
需要注意的是，这里用到了回溯，一个add对应一个remove

（3）代码：

private List<Integer> res = new ArrayList<>();
private int sum = 0;
public int sumNumbers(TreeNode root) {
    if (null == root) {
        return 0;
    }
    add(root);
    return sum;
}


private void add(TreeNode root) {
    if (null == root) {
        return;
    }

    // 回溯add值
    res.add(root.val);
    if (root.left == null && root.right == null) {
        int revert = revert(res);
        sum += revert;
    }

    add(root.left);
    add(root.right);
  	// 回溯remove值
    if (res.size() > 0) {
        res.remove(res.size() - 1);
    }
}

private int revert(List<Integer> res) {
    if (res.size() == 0) {
        return 0;
    }
    int l = 1;
    int count = 0;
    for (int i = res.size() - 1; i >= 0; i--) {
        count += l * res.get(i);
        l = l * 10;
    }
    return count;
}

刷题/Leetcode > 树

#LeetCode #树 #medium

树medium专题

http://coder-xieshijie.cn/2023/02/10/刷题/树medium专题/

作者

谢世杰

发布于

2023年2月10日

更新于

2023年2月27日

许可协议

回溯专题上一篇

树easy专题下一篇