450 Delete Node in a BST 刪除二叉搜索樹中的節(jié)點
Description:
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.
Follow up:
Can you solve it with time complexity O(height of tree)?
Example:
Example 1:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: 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 above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
Example 2:
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.
Example 3:
Input: root = [], key = 0
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
Each node has a unique value.
root is a valid binary search tree.
-10^5 <= key <= 10^5
題目描述:
給定一個二叉搜索樹的根節(jié)點 root 和一個值 key，刪除二叉搜索樹中的 key 對應(yīng)的節(jié)點，并保證二叉搜索樹的性質(zhì)不變费尽。返回二叉搜索樹（有可能被更新）的根節(jié)點的引用竿屹。
一般來說，刪除節(jié)點可分為兩個步驟：
首先找到需要刪除的節(jié)點；
如果找到了，刪除它。
說明：
要求算法時間復(fù)雜度為 O(h)搏熄，h 為樹的高度。
示例 :
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
給定需要刪除的節(jié)點值是 3暇赤，所以我們首先找到 3 這個節(jié)點心例，然后刪除它。
一個正確的答案是 [5,4,6,2,null,null,7], 如下圖所示鞋囊。
5
/ \
4 6
/ \
2 7
另一個正確答案是 [5,2,6,null,4,null,7]止后。
5
/ \
2 6
\ \
4 7
思路:
遞歸
先通過二叉搜索樹的性質(zhì)查找到需要刪去的節(jié)點
- 如果該節(jié)點左右孩子中有一個為空, 則用另一個子樹代替刪除節(jié)點即可
- 如果該節(jié)點為葉子節(jié)點, 直接刪除即可
- 如果該節(jié)點兩個孩子都存在, 則用右子樹中的最小值來代替該節(jié)點, 因為右子樹中的節(jié)點都大于待刪除節(jié)點, 所以這個最小值一定大于左子樹所有節(jié)點的值, 不會破壞二叉搜索樹的性質(zhì)
查找右子樹的最小值只需要一直往左走到底即可
時間復(fù)雜度O(h), 空間復(fù)雜度O(h), 其中 h為二叉搜索樹的高度, 最小為平衡二叉樹時 h = lgn
代碼:
C++:
/**
* 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 root;
if (root -> val > key) root -> left = deleteNode(root -> left, key);
else if (root -> val < key) root -> right = deleteNode(root -> right, key);
else
{
if (!root -> left or !root -> right) root = root -> left ? root -> left : root -> right;
else
{
TreeNode *cur = root -> right;
while (cur -> left) cur = cur -> left;
root -> val = cur -> val;
root -> right = deleteNode(root -> right, cur -> val);
}
}
return root;
}
};
Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
if (root.val > key) root.left = deleteNode(root.left, key);
else if (root.val < key) root.right = deleteNode(root.right, key);
else {
if (root.left == null || root.right == null) root = root.left == null ? root.right : root.left;
else {
TreeNode cur = root.right;
while (cur.left != null) cur = cur.left;
root.val = cur.val;
root.right = deleteNode(root.right, cur.val);
}
}
return root;
}
}
Python:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if not root:
return None
if root.val > key:
root.left = self.deleteNode(root.left, key)
elif root.val < key:
root.right = self.deleteNode(root.right, key)
else:
if not root.left or not root.right:
root = root.left if root.left else root.right
else:
cur = root.right
while cur.left:
cur = cur.left
root.val = cur.val
root.right = self.deleteNode(root.right, cur.val)
return root
