450. Delete Node in a BST

Difficulty: Medium

Related Topics: Tree

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Follow up: Can you solve it with time complexity O(height of tree)?

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3\. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 10<sup>4</sup>].
• -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
• Each node has a unique value.
• root is a valid binary search tree.
• -10<sup>5</sup> <= key <= 10<sup>5</sup>

Solution

Language: Java

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

        if (key < root.val) {

            // 把已经处理过的左子树重新连接到根节点
            //
            //             5 <- root          5 
            //            / \                / \
            //  remove-> 3   7        ==>   1   7
            //          /
            //         1
            //
            root.left = deleteNode(root.left, key);    

        } else if (key > root.val) {

            // 同理，把已经处理过的右子树重新连接到根节点
            root.right = deleteNode(root.right, key);

        } else {

            // 处理删除操作
            // 要删除的节点分为三种情况，分别是:
            // 1. 叶子节点
            // 2. 右单分支节点
            // 3. 左单分支节点
            // 4. 双分支节点

            // 1. 叶子节点
            //
            //             5 <- root              5 
            //            / \                    / \
            //  remove-> 3   7        ==>      null 7
            //
            if (root.left == null && root.right == null) {
                return null;
            }


            // 2. (右) 单分支节点: 右子树的 root 节点变成新的根节点
            // 
            //      5 <- root                  5 
            //       \                          \
            //        7  <- remove     ==>       8 <- new right node  
            //       / \
            //     null 8
            //
            if (root.left == null) {
                return root.right;
            }

            // 3. (左) 单分支节点: 左子树的 root 节点变成新的根节点
            if (root.right == null) {
                return root.left;
            }

            // 4. 双分支节点: 找到右节点的最左边的节点，在这里是 (2)，
            //    然后把要删除节点的左分支接到 (2) 的左分支
            //
            //        5 <- root                               5
            //       /                                       /
            //      4 <- remove              3              3
            //     / \              ==>     /     ==>      /
            //    1   3                    2              2
            //       /                    /              /
            //      2                    1              1
            //
            if (root.left != null && root.right != null) {
                mostleft(root.right).left = root.left;
                return root.right;
            }
        }

        return root;
    }

    //递归获得最左的节点
    private TreeNode mostleft(TreeNode root) {
        if (root == null) return null;
        if (root.left == null) return root;

        return mostleft(root.left);
    }
}