Code & Func

第24天。

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:

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

Note: Time complexity should be O(height of tree).

Example:

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

4
    5
5
   / \
6
  3   6
7
 / \   \
8
2   4   7
9

10
Given key to delete is 3. So we find the node with value 3 and delete it.
11

12
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
13

14
    5
15
   / \
11 collapsed lines
16
  4   6
17
 /     \
18
2       7
19

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

22
    5
23
   / \
24
  2   6
25
   \   \
26
    4   7

水题，只要先在BST上做搜索，然后删除就好了，因为只是BST，所以可以不考虑平衡的问题：

left和right都为空：直接删除，返回nullptr即可
left和right都不为空：默认采用把右子树的节点拉上来的方式，即把左子树插入到右子树中，然后再返回right即可。
left和right有一个不为空，则返回不为空的子树即可。

则代码如下：

1
    TreeNode* deleteNode(TreeNode *node) {
2
        auto left = node->left, right = node->right;
3
        delete node;
4
        if (left && right) {
5
            auto temp = right;
6
            while(temp->left) {
7
                temp = temp->left;
8
            }
9
            temp->left = left;
10
            return right;
11
        }
12
        return (left ? left : (right ? right : nullptr));
13
    }
14
    TreeNode* deleteNode(TreeNode* root, int key) {
15
        if (root == nullptr) return nullptr;
9 collapsed lines
16
        else if (root->val == key) {
17
            return deleteNode(root);
18
        } else if (key >  root->val) {
19
            root->right = deleteNode(root->right, key);
20
        } else
21
            root->left = deleteNode(root->left, key);
22

23
        return root;
24
    }