Task

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. Note: Time complexity should be O(height of tree).

Examples

 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

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

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 following BST.

    5
   / \
  4   6
 /     \
2       7

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

    5
   / \
  2   6
   \   \
    4   7

Solution

  • 删除值为key的节点，首先要找到这个节点，从根节点开始搜索。未找到等于key的节点时，如下图：
    • 若当前节点a小于key，则进入右子树搜索
    • 若当前节点a大于key，则进入左子树搜索
    • 若当前节点a等于key，后面分析 leetcode450_1
  • 若找到了等于key的节点，即当前节点a等于key，如下图：
    • 若当前节点a没有子树，则直接删除节点a，并将指向它的指针置为空
    • 若当前节点a只有左子树，则让节点a的父节点接管其左子树，删除节点a
    • 若当前节点a只有右子树，则让节点a的父节点接管其右子树，删除节点a
    • 若当前节点a同时有左子树和右子树，后面分析 leetcode450_2
  • 若当前节点a等于key，且当前节点a同时有左子树和右子树，如下图：
  • 可在左子树中找最大的节点替换当前节点，也可在右子树中找最小的节点替换当前节点。不失一般性，选后者
  • 在当前节点a的右子树中找最小节点m，即是找a的右子树中最左边的节点m，它一定只有右子树或者没有子树
  • 两种实现：
    • 将节点a的值替换为m的值，此时树中有两个值为m的节点，再在a的右子树中递归地删除值为m的节点即可。由于m只有右子树，可直接跳到递归终点。（这种方法的缺点是：若之前有一个指针指向m，则删除m后该指针悬空）
    • 使用指针操作将节点m移动到节点a的位置上，再删除节点a。（若之前有一个指针指向m，操作后该指针仍有效） leetcode450_3
  • 时间复杂度：找到值为key的节点后或者直接让父节点接管子树，或者继续查找右子树的最小节点，故时间复杂度O(h)
  • 空间复杂度：取决于递归深度，O(h)
  • 第一种实现：
 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
45
46
47
48
49

// Runtime: 40 ms, faster than 37.88% of C++ online submissions for Delete Node in a BST.
// Memory Usage: 15.2 MB, less than 75.68% of C++ online submissions for Delete Node in a BST.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //递归终点
        if(!root) return nullptr;
        //向下搜索值为key的节点
        if(root->val<key)
            root->right=deleteNode(root->right,key);
        else if(root->val>key)
            root->left=deleteNode(root->left,key);
        //找到值为key的节点
        else{
            //当值为key的节点同时有左右子树
            if(root->left && root->right){
                //搜索右子树的最左边节点，即最小节点
                TreeNode *min=root->right;
                while(min->left)
                    min=min->left;
                //为值为key的节点重新赋值
                root->val=min->val;
                //删掉右子树的最小节点（重复）
                root->right=deleteNode(root->right,min->val);
            }
            //当值为key的节点或者只有左子树、或者只有右子树、或者二者皆无
            else{
                //三种情况都可用newroot表示其子树
                TreeNode *newroot=(root->left)?(root->left):(root->right);
                //删除该节点并返回其子树（由于是被父节点递归调用，故效果是让其父节点接管其子树）
                root->left=root->right=nullptr;
                delete root;
                return newroot;
            }
        }
        return root;
    }
};
  • 第二种实现：
 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
45
46
47
48
49
50

// Runtime: 36 ms, faster than 65.89% of C++ online submissions for Delete Node in a BST.
// Memory Usage: 15.3 MB, less than 64.99% of C++ online submissions for Delete Node in a BST.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return nullptr;
        if(root->val<key)
            root->right=deleteNode(root->right,key);
        else if(root->val>key)
            root->left=deleteNode(root->left,key);
        //找到值为key的节点
        else{
            TreeNode *newroot;
            //当值为key的节点同时有左右子树
            if(root->left && root->right){
                //寻找右子树的最左节点newroot及其父节点parent
                TreeNode *parent=root;
                newroot=root->right;
                while(newroot->left){
                    parent=newroot;
                    newroot=newroot->left;
                }
                //当右子树的最左节点不是右子树的根节点时（即右子树不是只有一个节点）
                //交换指针
                if(parent!=root){
                    parent->left=newroot->right;
                    newroot->right=root->right;
                }
                newroot->left=root->left;
            }
            //当值为key的节点或者只有左子树、或者只有右子树、或者二者皆无
            else
                newroot=(root->left)?(root->left):(root->right);
            delete root;
            return newroot;
        }
        return root;
    }
};