Title Description

Given the root node root and a value key of a binary search tree, delete the node corresponding to the key in the binary search tree and ensure that the properties of the binary search tree remain unchanged. Returns a reference to the root node of a binary search tree that may be updated.

Generally speaking, deleting a node can be divided into two steps:

1. First, find the node to delete;
2. If found, delete it.

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
 Output:[5,4,6,2,null,null,7]
Explanation: given that the value of the node to be deleted is 3, we first find the node 3, and then delete it.
A correct answer is [5,4,6,2,null,null,7], 

Another correct answer is [5,2,6,null,4,null,7]. 

Example 2:

input: root = [5,3,6,2,4,null,7], key = 0
 output: [5,3,6,2,4,null,7]
explain: A binary tree does not contain a node with a value of 0

Example 3:

input: root = [], key = 0
 output: []

Tips:

• Range of nodes [0, 104]
• -105 <= Node.val <= 105
• Node value unique
• root is a legal binary search tree
• -105 <= key <= 105

Advanced: the time complexity of the algorithm is O(h), and h is the height of the tree.

It is also a binary tree, or a binary search tree. I remember just a few days ago I reflected on my lack of basic knowledge here. I didn't expect to face it again today.

Look at the official solution as usual.

official

The official uses two methods, one is recursion and the other is iteration.

We only analyze recursion. The principle of iteration is the same as recursion, but the implementation ideas are different.

Here is a detailed classification discussion:

First discuss whether the current node is null, and then in root When Val exists, compared with key, Val greater than key continues to recurse on the left subtree, and val less than key continues to recurse on the right subtree.

When val equals key, the situation is more complicated, so a classification discussion is nested:

When the current root has no left and right subtrees, that is, when the root is a leaf node, null is returned directly, indicating that the node has been deleted and there is no val; When there are only left / right subtrees, the left / right subtree is returned directly, indicating that the current root is deleted and replaced by the root of the left / right subtree.

When both the left and right subtrees of root exist, things become more complicated. The official solution is to find the smallest node success of the right subtree to replace root (or the largest node of the left subtree). This operation requires deleting the node success in the right subtree first, and then replacing root with success to complete the replacement operation.

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

After reading the solutions of other leaders in the review area, I found some strange ideas.

It also constructs binary search trees. The official structure is very regular, that is, the code process recurses too much, consumes too much space, and is not easy to understand. However, this topic only requires a legal BST, and there is no regulation on how to sort, so we have the following ideas:

First, find the smallest node t of the right subtree, then connect the entire left subtree of root to the left of t, and then use the right subtree to replace the original root, which is equivalent to eliminating the process of calling recursion again in this part.

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

Today, I briefly understood the deletion process of BST, and analyzed two slightly different ways of solving problems. More than one kind of thinking can deepen the understanding of knowledge. In addition, deletion is also a practical operation, which may be applied in future life.