代码随想录-刷题第二十三天

669.修剪二叉搜索树

题目链接：669. 修剪二叉搜索树

思路：确定递归函数定义，根据定义去构造二叉搜索树。

class Solution {
   
    // 定义：删除 BST 中小于 low 和大于 high 的所有节点，返回结果 BST
    public TreeNode trimBST(TreeNode root, int low, int high) {
   
        if (root == null) return null;

        if (root.val < low) {
   
            // 直接返回 root.right
            // 等于删除 root 以及 root 的左子树
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
   
            // 直接返回 root.left
            // 等于删除 root 以及 root 的右子树
            return trimBST(root.left, low, high);
        }

        // 闭区间 [lo, hi] 内的节点什么都不做
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

        return root;
    }
}

108.将有序数组转换为二叉搜索树

题目链接：108. 将有序数组转换为二叉搜索树

思路：题目要求构成一个左右平衡的二叉树，先找到数组的中间节点，作为根节点，然后根据中间节点左边的数组构建左子树，中间节点右边的数组构建右子树。递归过程中可以看出循环不变量的重要性！

class Solution {
   
    public TreeNode sortedArrayToBST(int[] nums) {
   
        return build(nums, 0, nums.length - 1);
    }
    // 左闭右闭区间[left, right]
    TreeNode build(int[] nums, int left, int right){
   
        if(left > right){
   
            return null;
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, left, mid - 1);
        root.right = build(nums, mid + 1, right);
        return root;
    }
}

538.把二叉搜索树转换为累加树

题目链接：538. 把二叉搜索树转换为累加树

思路：维护一个外部累加变量 sum，在遍历 BST 的过程中增加 sum，同时把 sum 赋值给 BST 中的每一个节点，就将 BST 转化成累加树了。但是注意顺序，正常的中序遍历顺序是先左子树后右子树，这里需要反过来，先右子树后左子树。

class Solution {
   
    public TreeNode convertBST(TreeNode root) {
   
        traverse(root);
        return root;
    }

    // 记录累加和
    int sum = 0;
    void traverse(TreeNode root) {
   
        if (root == null) {
   
            return;
        }
        // 注意：先右子树后左子树
        traverse(root.right);
        // 维护累加和
        sum += root.val;
        // 将 BST 转化成累加树
        root.val = sum;
        traverse(root.left);
    }
}

二叉树总结

二叉树题目中的注意点

1、二叉树中大部分题目使用递归，要想到递归三部曲

（1、确定返回值，参数。2、确定终止条件。3、确定单层逻辑。）

2、二叉树的题目遍历顺序非常重要，拿到一个题目首先要确定遍历顺序。

3、遇到二叉搜索树的题目，不要忘记二叉搜索树中序遍历的特性。

二叉树题目类型

1、二叉树构造类题目，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。

2、求解普通二叉树属性，一般是后序，一般要通过递归函数的返回值做计算。

3、求解二叉搜索树属性，一定要优先考虑中序遍历的特性。

注意在普通二叉树的属性中，一般为后序，但是单纯求深度就用前序，二叉树：找所有路径也用了前序，这是为了方便让父节点指向子节点。所以求普通二叉树的属性还是要具体问题具体分析。