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

### 题目描述

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) – 树最大深度
Licensed under CC BY-NC-SA 4.0
Built with Hugo
Theme Stack designed by Jimmy