题目描述
题目链接：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].
解题思路
有关于树的问题用递归的方式都比较好解决，针对这道题我们需要删除指定节点。最简单的方法是：首先通过二叉搜索树的性质找出该节点，然后分以下情况讨论：
- 该节点为子节点，没有任何子树，直接删除即可
- 该节点只有一子树（左/右子树），将该节点换成不为空的子树根即可
- 该节点有两子树，我们可以选择将该节点的值换成左子树最大值/右子树最小值，然后删除被替换的节点即可。由于左子树最大节点肯定没有右分支；右子树最小节点肯定没有左分支，所以会回到前一种情况。
代码如下：
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) – 树最大深度