450. Delete Node in a BST

,

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            // key == root.val
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                // 同时存在左右子树，将右子树嫁接至左子树
                TreeNode leftRoot = root.left;
                TreeNode tmp = leftRoot;
                while (tmp.right != null) {
                    tmp = tmp.right;
                }
                tmp.right = root.right;
                return leftRoot;
            }
        }

        return root;
    }
}

该解法将增加树的高度，不建议使用。

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    private TreeNode predecessor(TreeNode node) {
        TreeNode left = node.left;
        while (left.right != null) {
            left = left.right;
        }
        return left;
    }

    private TreeNode successor(TreeNode node) {
        TreeNode right = node.right;
        while (right.left != null) {
            right = right.left;
        }
        return right;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left != null) {
                TreeNode predecessor = predecessor(root);
                root.val = predecessor.val;
                root.left = deleteNode(root.left, predecessor.val);
            } else {
                // root.left == null && root.right != null
                TreeNode successor = successor(root);
                root.val = successor.val;
                root.right = deleteNode(root.right, successor.val);
            }
        }

        return root;
    }
}

References

450. Delete Node in a BST