Delete Node in BST

• Delete Node in BST

• Split BST

Delete Node in BST

• 可以实现Iterative O(1) space solution

• 第一步找到需要删除的node, and keep track of prev node

• 然后实现deleteRootNode(TreeNode root) 功能，返回新的子数

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode prev = null, cur = root;
        while (cur != null && cur.val != key) {
            prev = cur;
            if (cur.val < key) {
                cur = cur.right;
            } else if (cur.val > key) {
                cur = cur.left;
            }
        }
        if (prev == null) return deleteRoot(root);
        if (prev.left == cur) {
            prev.left = deleteRoot(cur);
        } else {
            prev.right = deleteRoot(cur);
        }
        return root;
    }

    // delete the root node of the tree, then return new tree structure
    //find the min treenode from rightsubtree
    private TreeNode deleteRoot(TreeNode root) {
        if (root == null) return null;
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        TreeNode prev = null, cur = root.right;
        while (cur.left != null) {
            prev = cur;
            cur = cur.left;
        }
        cur.left = root.left;
        if (root.right != cur) {
            prev.left = cur.right;
            cur.right = root.right;
        }
        return cur;
    }
}

Split BST

• 遇到tree的题目首先要看是否可以递归

class Solution {
    public TreeNode[] splitBST(TreeNode root, int V) {
        if (root == null) return new TreeNode[2];
        if (root.val > V) {
            TreeNode[] left = splitBST(root.left, V);
            root.left = left[1];
            return new TreeNode[] {left[0], root};
        } else {
            TreeNode[] right = splitBST(root.right, V);
            root.right = right[0];
            return new TreeNode[] {root, right[1]};
        }
    }
}

TODO: iterative