Trim a Binary Search Tree

Question

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Solution

雖然還是卡卡的，但有寫出來，只是效率不好。原則上就是 iterate tree，然後判斷跟 L 與 R 之間的關係。在思考過程中，對於 recursion function 要不要回傳值猶豫了一陣子，先附上自己的 code

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

        TreeNode newRoot = new TreeNode(0);
        helper(root, L, R, newRoot);
        return newRoot;
    }

    public TreeNode helper(TreeNode root, int low, int high, TreeNode newRoot) {
        if (root == null) {
            return null;
        }

        if (root.val >= low && root.val <= high) {
            newRoot.val = root.val;
            newRoot.left = helper(root.left, low, high, new TreeNode(0));
            newRoot.right = helper(root.right, low, high, new TreeNode(0));
        } else if (root.val >= low) {
            newRoot = helper(root.left, low, high, newRoot);
        } else if (root.val <= high) {
            newRoot = helper(root.right, low, high, newRoot);
        }

        return newRoot;
    }

再附上解答的 code

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

    if (root.val > R) {
        return trimBST(root.left, L, R);
    }

    if (root.val < L) {
        return trimBST(root.right, L, R);
    }

    root.left = trimBST(root.left, L, R);
    root.right = trimBST(root.right, L, R);

    return root;
}