669. Trim a Binary Search Tree修剪二叉搜索树

［抄题］：

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Input: 
    1
   / 
  0   2

  L = 1
  R = 2

Output: 
    1
      
       2

Example 2:

Input: 
    3
   / 
  0   4
   
    2
   /
  1

  L = 1
  R = 3

Output: 
      3
     / 
   2   
  /
 1

[暴力解法]：

时间分析：

空间分析：

［奇葩输出条件］：

判断节点的值是否不在范围内，而非节点是否非空。第一次见，要注意。

［奇葩corner case］：

［思维问题］：

［一句话思路］：

分左右之后为了保持一路的继承关系，还是左节点traverse左节点

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

traverse中的主操作是对root一个节点进行的，操作完直接返回。分左右之后为了保持一路的继承关系，还是左节点traverse左节点，操作完还有下一步，不用返回。

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

traverse中的主操作是对root一个节点进行的，操作完直接返回。

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

左右是节点，因为左右子树都是新建的

［关键模板化代码］：

//trim left
        root.left = trimBST(root.left, L, R);
        //trim right
        root.right = trimBST(root.right, L, R);

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        //corner case: if root is null
        if (root == null) {
            return null;
        }
        //corner case: if left or right is out of bound
        if (root.val < L) {
            return trimBST(root.right, L, R);
        }
        if (root.val > R) {
            return trimBST(root.left, L, R);
        }
        //trim left
        root.left = trimBST(root.left, L, R);
        //trim right
        root.right = trimBST(root.right, L, R);
        //return
        return root;
    }
}

View Code