669. 修剪二叉搜索树（BST）

669. 修剪二叉搜索树

• 题目
• 解题思路
• 代码

题目

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

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

提示：

• 树中节点数在范围 [1, 104] 内
• 0 <= Node.val <= 104
• 树中每个节点的值都是唯一的
• 题目数据保证输入是一棵有效的二叉搜索树
• 0 <= low <= high <= 104

解题思路

BST问题最核心的框架就是“明确一个节点要做的事情，剩下的事情交给递归框架”

这题中“一个节点该做的事情”就是 和low、high比较。

• 如果root.val>high，证明root的右子树都比high大，裁剪掉它的右子树，然后再遍历它剩下的那颗右子树。
• 如果root.val<low，证明root的左子树都比low小，裁剪掉它的左子树，然后再遍历它剩下的那颗左子树。

代码

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root==null){
            return null;
        }
        if(root.val<low){//如果root 小于low，那么root的左子树也一定都小于low，所以把左子树都裁剪掉
        root=root.right;

         return trimBST(root,low,high);//继续遍历裁剪后的节点的右子树
        }
        if(root.val>high){
             root=root.left;
            return trimBST(root,low,high);
        }


        // 这条线以上是明确一个节点该做的事
        /************************************************************/
        //线以下是把剩下的事抛给递归框架


        //如果目前节点的值满足范围，就去遍历它的左子树和右子树看它们是不是满足要求
        root.left=trimBST(root.left,low,high);
        root.right=trimBST(root.right,low,high);

        return root;
    }
}