代码随想录算法训练营第二十二天 | LeetCode 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树

1. LeetCode 669. 修剪二叉搜索树

1.1 思路

1. 在上面450. 删除二叉搜索树中的节点这题中有一种情况我们是把删除节点的右子树返回给删除节点的父节点，让父节点直接指向被删节点的右子树。
2. 递归函数的参数和返回值：就是本题给的函数，返回的是修剪完后新的二叉树的根节点，参数是root，左右边界low和high
3. 终止条件：如果遍历到null，就return null；
4. 常见误区：如果root的值比low小或者比high大就返回null，如果按照这样删除，那么root的父节点就直接指向空了，如果root还有左右孩子就直接无法连接了。
5. 正确思路：如果发现当前节点的值比左边界小或者比右边界大，其右子树是可能符合边界条件的，就应该先把右子树接着遍历
6. 以下是单层递归的逻辑：
7. 判断如果root的值比low小，就接着向右遍历，right=函数(root.right, low, high)，含义是把被删节点的右子树修剪完以后返回给被删节点的父节点，然后返回right；这里判断后不能直接return root.right，因为root的右子树不一定完全符合题目的边界要求，因此需要遍历。
8. 判断如果root的值比high大，就接着向左遍历，left=函数(root.left, low, high)，含义是把被删节点的左子树修剪完以后返回给被删节点的父节点，然后返回left；这里判断后不能直接return root.left，因为root的左子树不一定完全符合题目的边界要求，因此需要遍历。
9. 接着就是左root.left=函数(root.left, low, high)；然后是右root.right=函数(root.right, low, high)；return root。root在上面处理过了

1.2 代码

//
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        // root在[low,high]范围内
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

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

2.1 思路

1. 关于构造二叉树，在106. 从中序与后序遍历序列构造二叉树这题中讲解过，整体思路是先选取一个中间节点，然后将数组分为左区间和右区间，递归遍历左区间构造左子树和遍历右区间构造右子树。
2. 本题中，也只有选取数组中间的数作为中间节点，左区间和右区间数量才相同，然后左区间也选中间然后分割左右区间，右区间也选中间然后分割左右区间。如果数组长度是偶数，中间有两个数，其实选哪个都可以，只是取靠左的那个数和靠右的那个数构造出来的树结构不一样而已。
3. 递归函数的参数和返回值：参数是nums数组，左边界，右边界。返回值就是构造出来的二叉树的根节点。定义区间的时候是左闭右闭还是左闭右开，这点要注意很重要！我们要全部统一定义，这里我定义的是左闭右闭的区间
4. 终止条件：如果left>right就是一个非法区间了，因为我这里定义的是左闭右闭，left==right是一个合法区间，只是这里是只有一个节点，那可能是叶子节点，但也符合题意的，因此我们就left>right时返回null即可
5. 单层递归的逻辑：中间节点的位置mid=(left+right)/2；然后是构造二叉树，root=新的节点，把nums[mid]赋值给它；然后root.left=函数(nums, left, mid-1)，因为是左闭右闭的区间，所以mid要减1，mid-1这个位置是包含右边界的。这个函数的含义是在这个数组下，下标是left和mid-1所构造的二叉树的根节点返回过来给root的左子树；然后root.right=函数(nums, mid+1, right)，因为是左闭右闭的区间，所以mid要+1，mid+1这个位置是包含左边界的。这个函数的含义是在这个数组下，下标是mid+1和right所构造的二叉树的根节点返回过来给root的右子树。然后返回root即可

2.2 代码

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

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

3.1 思路

1. 本题的累加方式是右中左，也就是反中序遍历，按照中序遍历的方式从右开始加就看懂了
2. 本题我们要从后往前加，如何从最大的节点开始倒序遍历呢？也就是右中左。那如何当前节点跟前一个节点相加呢？双指针！root指向当前节点，pre指向前一个节点的值，然后逐渐相加，逐渐往回遍历
3. 递归函数的参数和返回值：要先定义一个全局变量int pre=0，直接定义成值就好，不用是节点，最开始root是指向最大的节点，pre=0，root.val+=pre，最开始是不变的。定义个新函数，返回值void，因为本题不需要返回值返回什么，参数就是传入根节点
4. 终止条件：遇到空节点就return了
5. 单层递归的逻辑：因为是右中左，因此先往右遍历，travelsal(root.right)；然后就是中的逻辑，就是root.val+=pre，然后pre=root.val，就更新pre，能让下一次root指向下一个节点时，pre能表示root的前一个节点的值；然后是再往左遍历，travelsal(root.left)。最后return即可

3.2 代码

//
class Solution {
    int sum;
    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        convertBST1(root);
        return root;
    }
    // 按右中左顺序遍历，累加即可
    public void convertBST1(TreeNode root) {
        if (root == null) {
            return;
        }
        convertBST1(root.right);
        sum += root.val;
        root.val = sum;
        convertBST1(root.left);
    }
}