题目名称

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

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

题解

这个题，还是在强调，问题本身，就是答案的核心，三种遍历都是递归，而递归的本质就是用相同的方式处理子问题，做完#776后，可以再感受一下，做这种二叉树的题目，什么是第一要素。

原本想着，是不是先要用low或者用high做约束，然后二分搜索到某一个特定节点，再嫁接之类的，或者用中序遍历性质，再怎么怎么处理。如果这么想，其实是固定了对BST的处理模式，陷入到这个模式这个题目就不太好做，反而要打开思路，看看root的值和给的low-high范围有啥关系。

打开思路以后，其实就会发现，root可能会在范围内，也有可能不在，讨论一下：

如果在范围内，那么说明root是要保留的，也就是说不用处理root，处理左右子树就可以了。
如果不再范围内，假如root-val > low，且根据BST性质，就会发现，左子树和root都在区间外，要保留的只可能是处理后的右子树。
所以，做这种题，就是先考虑：

是否能用题目的定义
如果可以用，那么是否可以用题目定义处理子问题（子树）
如果可以处理子问题，是否可以用子问题结果凑出原定义
多说一句，因为本身题目给的API就是问题的答案，如果可以凑出来，实际上就是求解过程。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {TreeNode}
 */
var trimBST = function(root, low, high) {
  const bfs = (tree) => {
    if(tree.val >= low && tree.val <= high) {
      tree.left && (tree.left = bfs(tree.left))
      tree.right && (tree.right = bfs(tree.right))
      return tree
    } else {
      if(tree.val < low) {
        return tree.right && (right = bfs(tree.right))
      }
      if(tree.val > high) {
        return tree.left && (left = bfs(tree.left))
      }
    }
  }
  return bfs(root)
};