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

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

    分析:此题的重点在于如何将不符合条件的节点给移除,第一时间想到的是直接设为空值不行吗?当然不行!因为这个节点的左子树或右子树有可能是符合条件的,所以这种方法是不行的,那么应该采取的方法是递归这个节点下面的子树,判断是否符合条件。如代码的加粗部分显示。

    参考代码:
    public TreeNode trimBST(TreeNode root, int low, int high) {
    return sup(root,low,high);
    }
    private TreeNode sup(TreeNode root,int low,int high){
    if(root==null) return null;
    if(root.val<low){
    TreeNode right = sup(root.right,low,high);
    return right;
    }
    if(root.val>high){
    TreeNode left=sup(root.left,low,high);
    return left;
    }
    root.left=sup(root.left,low,high);
    root.right=sup(root.right,low,high);
    return root;
    }