二叉搜索树的修改与构造 - leetcode-669：修建二叉搜索树 - 《算法珠玑》

问题
解法一：递归
解法二：迭代法

问题

给你二叉搜索树的根节点 root，同时给定最小边界low和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。可以证明，存在唯一的答案
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变

示例 1：
leetcode-669：修建二叉搜索树 - 图1
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：
leetcode-669：修建二叉搜索树 - 图2
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

示例 3：
输入：root = [1], low = 1, high = 2
输出：[1]

示例 4：
输入：root = [1,null,2], low = 1, high = 3
输出：[1,null,2]

示例 5：
输入：root = [1,null,2], low = 2, high = 4
输出：[2]

解法一：递归

直接想法就是：递归处理，然后遇到 root.val < low || root.val > high 的时候直接return null

不难写出如下代码：

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null || root.val < low || root.val > high) 
            return null;
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
};

然而[1, 3]区间在二叉搜索树的中可不是单纯的节点3和左孩子节点0就决定的，还要考虑节点0的右子树
leetcode-669：修建二叉搜索树 - 图3
所以以上的代码是不可行的！

从图中可以看出需要重构二叉树，想想是不是本题就有点复杂了

其实不用重构那么复杂

在上图中我们发现节点0并不符合区间要求，那么将节点0的右孩子节点2直接赋给节点3的左孩子就可以了（就是把节点0从二叉树中移除），如图：
leetcode-669：修建二叉搜索树 - 图4
理解了最关键部分了我们再递归三部曲：

确定递归函数的参数以及返回值
- 这里我们为什么需要返回值呢？因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是从二叉树中移除节点）的操作。但是有返回值，更方便，可以通过递归函数的返回值来移除节点
```
TreeNode trimBST(TreeNode root, int low, int high)
```

**确定终止条件

修剪的操作并不是在终止条件上进行的，所以就是遇到空节点返回就可以了
```
if (root == null) return null;
```

确定单层递归的逻辑

如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点

if (root.val < low) {
TreeNode right = trimBST(root.right, low, high); // 寻找符合区间[low, high]的节点
return right;
}

如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点

if (root.val > high) {
TreeNode left = trimBST(root.left, low, high); // 寻找符合区间[low, high]的节点
return left;
}

接下来要将下一层处理完左子树的结果赋给root.left，处理完右子树的结果赋给root.right ，最后返回root节点，代码如下：

root.left = trimBST(root.left, low, high); // root.left接入符合条件的左孩子
root.right = trimBST(root.right, low, high); // root.right接入符合条件的右孩子
return root;

此时大家是不是还没发现这多余的节点究竟是如何从二叉树中移除的呢？

如下代码相当于把节点0的右孩子（节点2）返回给上一层

if (root.val < low) {
    TreeNode right = trimBST(root.right, low, high); // 寻找符合区间[low, high]的节点
    return right;
}

然后如下代码相当于用节点3的左孩子把下一层返回的节点0的右孩子（节点2）接住

root.left = trimBST(root.left, low, high);

此时节点3的右孩子就变成了节点2，将节点0从二叉树中移除了

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null ) return null;
        if (root.val < low) {
            TreeNode right = trimBST(root.right, low, high); // 寻找符合区间[low, high]的节点
            return right;
        }
        if (root.val > high) {
            TreeNode left = trimBST(root.left, low, high); // 寻找符合区间[low, high]的节点
            return left;
        }
        root.left = trimBST(root.left, low, high); // root.left接入符合条件的左孩子
        root.right = trimBST(root.right, low, high); // root.right接入符合条件的右孩子
        return root;
    }
};

精简之后代码如下

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.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

解法二：迭代法

因为二叉搜索树的有序性，不需要使用栈模拟递归的过程

在剪枝的时候，可以分为三步：

将root移动到[L, R]范围内，注意是左闭右闭区间
剪枝左子树

剪枝右子树

class Solution {
  public TreeNode trimBST(TreeNode root, int L, int R) {
      if (!root) return null;
      // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
      while (root.val < L || root.val > R) {
          if (root.val < L) 
              root = root.right; // 小于L往右走
          else root = root.left; // 大于R往左走
      }
      TreeNode cur = root;
      // 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
      while (cur != null) {
          while (cur.left && cur.left.val < L) {
              cur.left = cur.left.right;
          }
          cur = cur.left;
      }
      cur = root;
      // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
      while (cur != null) {
          while (cur.right && cur.right.val > R) {
              cur.right = cur.right.left;
          }
          cur = cur.right;
      }
      return root;
  }
}