修剪二叉搜索树likou669

乍一看，好难，再看，卧槽，不会。。。。。

相对于以往来说，有进步了，居然一下就看出来坑点在哪里。

不过还是自己太菜了，没解决掉、、、、、

来卡卡大佬是如何解决的吧：

 删除逻辑当然是根节点小于left或者根节点大于right,我当时就在这里发现了这个坑点如下图：

 

如果按照上面的逻辑，2、3的节点就没了，是错的。

正确的解法是：

 根节点小于lef时，继续往右节点判断，因为右节点大于根节点，有可能满足区间条件。

根节点大于right时，继续往左边节点判断，因为右节点小于根节点，有可能满足区间条件。

我当时咋就没想出来呢！！！

上代码：

    public TreeNode trimBST(TreeNode root, int left, int right) {
        return dfs(root, left, right);
    }
 
    private TreeNode dfs(TreeNode root, int left, int right) {
        if (root == null) {
            return null;
        }
        if (root.val < left) {
            return dfs(root.right, left, right);
        } 
        if (root.val > right) {
            return dfs(root.left, left, right);
        }
        root.left = dfs(root.left, left, right);
        root.right = dfs(root.right, left, right);
        return root;
    }

 写了40天二叉树了，真是煎熬得很、、、、、