题目描述

给定一个二叉搜索树，同时给定最小边界 L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在 [L, R] 中 (R>=L)。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

样例

输入:
1
/ \
0 2

L = 1
R = 2

输出:
1
\
2

输入:
3
/ \
0 4
\
2
/
1

L = 1
R = 3

输出:
3
/
2
/
1

算法1

错误例子，没看清楚题目，题目返回的树，是在原树上做删除操作，而不是重建一个BST,所以不能先按照L，R先过滤，得到有序数组，然后按照LeeCode108，对有序数组重建BST，下面是错误代码

Java代码

public class Solution {

    List<Integer> l = new ArrayList<>();

    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) {
            return null;
        }

        inOrder(root, L, R);
        for (int i = 0; i < l.size(); i++) {
            System.out.print(l.get(i) + " ");
        }
        return sortedArrayToBST(l);
    }

    private TreeNode sortedArrayToBST(List<Integer> l) {
        int n = l.size();
        if (n == 0) {
            return null;
        }

        return dfs(l, 0, n - 1);
    }

    private TreeNode dfs(List<Integer> list, int l, int r) {
        if (l < r) {
            int mid = (r - l) / 2 + l;
            TreeNode root = new TreeNode(list.get(mid));
            root.left = dfs(list, l, mid - 1);
            root.right = dfs(list, mid + 1, r);
            return root;
        } else if (l > r) {
            return null;
        } else {
            return new TreeNode(list.get(l));
        }
    }

    private void inOrder(TreeNode root, int L, int R) {
        if (root == null) {
            return;
        }

        inOrder(root.left, L, R);
        if (root.val >= L && root.val <= R) {
            l.add(root.val);
        }
        inOrder(root.right, L, R);
    }

}

算法2

正确方法如下: O(n)

Java代码

class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) {
            return null;
        }

        // root val 小于 L, 裁掉root及其左子树
        if (root.val < L) {
            return trimBST(root.right, L, R);
        }

        // root val 大于 R, 裁掉root及其右子树
        if (root.val > R) {
            return trimBST(root.left, L, R);
        }
        // 当前root满足[L,R], 两边继续裁
        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}