0%

[Leetcode]450. Delete Node in a BST(C++)

题目描述

题目链接:450. Delete Node in a BST

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).

例子

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

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.

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

解题思路

有关于树的问题用递归的方式都比较好解决,针对这道题我们需要删除指定节点。最简单的方法是:首先通过二叉搜索树的性质找出该节点,然后分以下情况讨论:

  • 该节点为子节点,没有任何子树,直接删除即可
  • 该节点只有一子树(左/右子树),将该节点换成不为空的子树根即可
  • 该节点有两子树,我们可以选择将该节点的值换成左子树最大值/右子树最小值,然后删除被替换的节点即可。由于左子树最大节点肯定没有右分支;右子树最小节点肯定没有左分支,所以会回到前一种情况。

代码如下:

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
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
// case 0: tree not exist, return nullptr
if (!root) return nullptr;

if (root->val > key) {
// case 1: target node is smaller than root, search it on left subtree
root->left = deleteNode(root->left, key);
} else if (root->val < key) {
// case 2: target node is larger than root, search it on left subtree
root->right = deleteNode(root->right, key);
} else {
// case 3.1: target node is root, if one of its subtree is empty;
// we can replace root with the other subtree's root
if (!root->left || !root->right) {
root = (root->left) ? root->left : root->right;
} else {
// case 3.2: two of its subtrees exists
// we replace root with the smallest node of its right subtree, then delete that node
TreeNode *target = root->right;
while (target->left) target = target->left;
root->val = target->val;
root->right = deleteNode(root->right, target->val);
}
}
return root;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(k) — 树最大深度