Poison

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
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 {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                // 寻找右子树中的最小值
                TreeNode right = root.right;
                TreeNode node = right;
                while (node.left != null) {
                    node = node.left;
                }
                node.left = root.left; // 把左树挂在右子树上
                return right; // 返回右子树作为新的根节点
            }
        }

        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;
    }
}
Reference

450. Delete Node in a BST