450. 删除二叉搜索树中的节点
450. 删除二叉搜索树中的节点
题目
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.
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
Follow up: Could you solve it with time complexity O(height of tree)
?
题目大意
给定一个二叉搜索树的根节点 root
和一个值 key
,删除二叉搜索树中的 key
对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
解题思路
删除一个节点,需要分几种情况讨论:
- 如果节点是叶子节点(没有左子树和右子树),直接删除即可。
- 如果节点只有一个子节点,将该节点替换为其子节点。
- 如果节点有两个子节点,找到右子树中的最小值节点,用该节点的值替换要删除的节点的值,然后递归地删除右子树中的最小值节点。
代码
/**
* @param {TreeNode} root
* @param {number} key
* @return {TreeNode}
*/
var deleteNode = function (root, key) {
if (!root) return null;
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) return root.right;
if (!root.right) return root.left;
const rightMin = findMin(root.right);
root.val = rightMin.val;
root.right = deleteNode(root.right, rightMin.val);
}
return root;
};
var findMin = function (root) {
while (root.left) {
root = root.left;
}
return root;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
776 | 拆分二叉搜索树 🔒 | 树 二叉搜索树 递归 1+ |