669. Trim a Binary Search Tree

题干简述：

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

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

二叉搜索树：该树每个节点都满足：当该节点存在子节点时，必然其左子节点的值小于它，而其右子节点的值必然大于它。

解题思路

本题的特色在于这个二叉树的性质，二叉检索树的优势在于，它是有顺序的，节点的左子树上的所有节点一定比它小，右子树上的所有节点一定比它大。结合本题的题意，要求我们把不在 [low, high] 这个闭区间内的节点裁剪掉，这个性质可就帮了我们大忙。

首先，让我们想想通过递归该如何解决这道题。思路还是一样，先思考一下递归的四大要素：

  • 输入参数：我们传递什么进去，本题自然是从 root 开始传递一个个节点进去；

  • 输出结果：我们返回什么出来给上一层使用，本题是返回在 [low, high] 区间内的有效节点；

  • 函数的功能/目的：这个递归函数是为了解决什么问题，本题是为了对二叉健检索树进行裁剪；

  • 终止条件：当输入参数满足什么结果时，代表我们已经执行到最底层，需要停止递归并开始逐层返回，本题自然是传入的节点为 null 时结束；

明确了上述的四点之后，我们还有明确一点，裁剪，是如何实现的?

本题的 node ，可以分为以下几种情况：

  1. node < low: 此时我们可以确认的是 node 的左子树(如果存在的话)，由于必然小于 node，也就必然小于 low，全都可以裁剪掉；但是由于 node 的右子树的节点均大于 node，导致我们不知道 node 的右子树中哪些节点是属于 [low, high] 这个区间内的，所以此时我们需要再对 node 的右子节点进行递归操作处理。如果 node 的右子树中存在属于 [low, high] 这个区间内的节点，我们需要将其返回给 node 的父节点，用来替换掉 node，毕竟 node 不满足条件，需要裁剪掉。
  2. node > high: 与上面说的 node < low 类似，不过这里我们要找到 node 的左子树中属于 [low, hight] 的这个节点并返回。
  3. node 属于 [low, high]: 此时 node 自身满足条件，我们就需要去判断 node 的子节点，是否属于这个区间了，就进入了下一层的递归。

综上，我们就得出了递归的解法。接下来，让我们看下迭代的解法。

迭代的解法，其本质还是和递归一样的，都是通过判断节点是否是在 [low, high] 区间内来进行裁剪的，不过迭代稍微要比递归要绕一点。首先，二叉树迭代解法经常是要我们通过队栈等数据结构来模拟递归的操作，一层层的处理节点，得益于二叉检索树的有序性，我们可以免去这一步（为什么可以免去呢？后面会说到）。首先，我们需要找到裁剪后的有效树的根节点，也就是我们迭代最上层的那个节点的位置。由于最终树的根节点必然是在 [low, high] 这个区间内的，根据二叉检索树的特殊性质，如果一个节点小于 low，其所有左子节点都小于 low，一个节点大于 high，所有右子节点都大于 high。我们要做的，就是一直循环比较，直到找到各个子树满足条件的节点，并返回即可。

题解

/**
 * 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) {
    if (!root) 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;
};

// 迭代解法
var trimBST = function(root, low, high) {
    if (!root) return null;
    while (root && (root.val < low || root.val > high)) {
        // 根据 root 相对区间位置，决定裁剪哪一个子树
        if (root.val < low) {
            root = root.right;
        } else {
            root  = root.left;
        }
    }
    let curr = root; // 存储便利时当前子树根节点
    while (curr !== null) {
        // curr 的左子节点小于 low 时,我们在其子树中一直向右找，找到第一个大于 low 的即可
        while (curr.left && curr.left.val < low) {
            curr.left = curr.left.right;
        }
        curr = curr.left; // 变更当前处理子树根节点，进一步向下层处理
    }
    curr = root; // 将当前处理子树重置为一开始的树，开始处理树的右子树
    while (curr !== null) {
        // 由于树的右子树都大于 root，因此我们需要处理掉其中大于 high 的节点。我们在其子树中一直向左找，找到第一个小于high的即可
        while (curr.right && curr.right.val > high) {
            curr.right = curr.right.left;
        }
        curr = curr.right;
    }
    return root;
};

Q.E.D.

Take it easy