給你二叉搜索樹(shù)的根節(jié)點(diǎn) root ，同時(shí)給定最小邊界low 和最大邊界 high。通過(guò)修剪二叉搜索樹(shù)，使得所有節(jié)點(diǎn)的值在[low, high]中。修剪樹(shù) 不應(yīng)該 改變保留在樹(shù)中的元素的相對(duì)結(jié)構(gòu) (即，如果沒(méi)有被移除，原有的父代子代關(guān)系都應(yīng)當(dāng)保留)。 可以證明，存在 唯一的答案 。
所以結(jié)果應(yīng)當(dāng)返回修剪好的二叉搜索樹(shù)的新的根節(jié)點(diǎn)。注意，根節(jié)點(diǎn)可能會(huì)根據(jù)給定的邊界發(fā)生改變。

舉例

提示：
樹(shù)中節(jié)點(diǎn)數(shù)在范圍 [1, 104] 內(nèi)
0 <= Node.val <= 104
樹(shù)中每個(gè)節(jié)點(diǎn)的值都是 唯一 的
題目數(shù)據(jù)保證輸入是一棵有效的二叉搜索樹(shù)
0 <= low <= high <= 104

解題思路：遞歸 或 迭代

方法一：遞歸（不難想到）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return null;
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        if(root.val < low) return root.right;
        else if(root.val > high) return root.left;
        else return root;
    }
}

方法二：迭代 ?

（基本思路有點(diǎn)像中序遍歷的普通迭代法）
① 首先找到滿(mǎn)足條件的根節(jié)點(diǎn)
② 從該根節(jié)點(diǎn)開(kāi)始，更新左子樹(shù)（查看是否會(huì)超出下界）
??一直向左孩子查找，直到找到不滿(mǎn)足條件的node【node和node的左子樹(shù)均不滿(mǎn)足要求→需要繼續(xù)判斷node的右子樹(shù)是否滿(mǎn)足要求】，并且找的過(guò)程中記錄下它的父節(jié)點(diǎn)parent，父節(jié)點(diǎn)的左孩子設(shè)置為node.right，并把當(dāng)前node設(shè)置為node.right，繼續(xù)重復(fù)上述過(guò)程【重新連接后要繼續(xù)判斷node是否滿(mǎn)足】，直到node == null。
③ 從該根節(jié)點(diǎn)開(kāi)始，更新右子樹(shù)（查看是否會(huì)超出上界）
??一直向右孩子查找，直到找到不滿(mǎn)足條件的node【node和node的右子樹(shù)均不滿(mǎn)足要求→需要繼續(xù)判斷node的左子樹(shù)是否滿(mǎn)足要求】，并且找的過(guò)程中記錄下它的父節(jié)點(diǎn)parent，父節(jié)點(diǎn)的右孩子設(shè)置為node.left，并把當(dāng)前node設(shè)置為node.left，繼續(xù)重復(fù)上述過(guò)程【重新連接后要繼續(xù)判斷node是否滿(mǎn)足】，直到node == null。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        // 1. 更新root
        while(root != null){
            if(root.val < low) root = root.right;
            else if(root.val > high) root = root.left;
            else break;
        }
        if(root == null) return root;
        // 此時(shí)root是有效的

        // 2. 更新root的左子樹(shù)，看是否有小于下界的
        TreeNode cur = root;
        while(cur != null){
            while(cur.left != null && cur.left.val < low){
                cur.left = cur.left.right; // 繼續(xù)修建右子樹(shù)
            }
            cur = cur.left;
        }

        // 3. 更新root的右子樹(shù)，看是否有大于下界的
        cur = root;
        while(cur != null){
            while(cur.right != null && cur.right.val > high){
                cur.right = cur.right.left; // 繼續(xù)修建右子樹(shù)
            }
            cur = cur.right;
        }

        return root;
    }
}