LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST
LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST
爱写bug
发布于 2020-03-25 17:39:12
发布于 2020-03-25 17:39:12
题目:
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
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.
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
Note: Time complexity should be O(height of tree).
示例:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
5
/ \
4 6
/ \
2 7
另一个正确答案是 [5,2,6,null,4,null,7]。
5
/ \
2 6
\ \
4 7
解题思路:
待删除节点在二叉树中的三种情况有:
- 如果目标节点没有子节点，我们可以直接移除该目标节点。
- 如果目标节只有一个子节点，我们可以用其子节点作为替换。
- 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。
另外二叉搜索树的中序遍历结果为从小到大顺序排列的; 删除节点如果不是叶子节点时, 则应把该节点的值替换为其右子树中最小的一个节点值 (删除节点的后驱节点); 删除节点如果不是叶子节点且无右子树时, 则应把该节点的值替换为其左子树中最大的一个节点值 (删除节点的前驱节点), 并在子树中递归删除刚刚替换的节点
你会发现, 二叉搜索树最小节点为该树的最左叶子; 最大节点为该树的最右叶子, 即:
- 如果 key > root.val，说明要删除的节点在右子树，root.right = deleteNode(root.right, key)。
- 如果 key < root.val，说明要删除的节点在左子树，root.left = deleteNode(root.left, key)。
- 如果 key == root.val，则该节点就是我们要删除的节点，则：
- 如果该节点是叶子节点，则直接删除它：root = null。
- 如果该节点不是叶子节点且有右节点，则用它的后继节点的值替代 root.val = successor.val，然后删除后继节点。
- 如果该节点不是叶子节点且只有左节点，则用它的前驱节点的值替代 root.val = predecessor.val，然后删除前驱节点。
Java:
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null)
return null;
// 找到待删除节点后的三种情况
if (key == root.val) {
// 删除节点为叶子节点
if (root.left == null && root.right == null)
root = null;
// 删除节点有右子树
else if (root.right != null) {
root.val = postNode(root.right);
root.right = deleteNode(root.right, root.val);
} else {// 删除节点无右子树但存在左子树
root.val = preNode(root.left);
root.left = deleteNode(root.left, root.val);
}
} else if (key > root.val)
root.right = deleteNode(root.right, key);
else
root.left = deleteNode(root.left, key);
return root;
}
// 找左子树的最大节点
private int preNode(TreeNode root) {
while (root.right != null)
root = root.right;
return root.val;
}
// 找右子树的最小节点
private int postNode(TreeNode root) {
while (root.left != null)
root = root.left;
return root.val;
}
}
Python:
class Solution:
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if not root:
return None
# 找到待删除节点后的三种情况
if root.val == key:
# 删除节点为叶子节点
if not root.left and not root.right:
root = None
# 删除节点有右子树
elif root.right:
root.val = self.postNode(root.right)
root.right = self.deleteNode(root.right, root.val)
# 删除节点无右子树但存在左子树
else:
root.val = self.preNode(root.left)
root.left = self.deleteNode(root.left, root.val)
elif key > root.val:
root.right = self.deleteNode(root.right, key)
else:
root.left = self.deleteNode(root.left, key)
return root
# 找左子树的最大节点
def preNode(self, root: TreeNode) -> int:
while root.right:
root = root.right
return root.val
# 找右子树的最小节点
def postNode(self, root: TreeNode) -> int:
while root.left:
root = root.left
return root.val
Golang:
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}
// 找到待删除节点后的三种情况
if root.Val == key {
// 删除节点为叶子节点
if root.Left == nil && root.Right == nil {
root = nil
} else if root.Right != nil {// 删除节点有右子树
root.Val = postNode(root.Right)
root.Right = deleteNode(root.Right, root.Val)
} else {// 删除节点无右子树但存在左子树
root.Val = preNode(root.Left)
root.Left = deleteNode(root.Left, root.Val)
}
} else if key > root.Val {
root.Right = deleteNode(root.Right, key)
} else {
root.Left = deleteNode(root.Left, key)
}
return root
}
// 找左子树的最大节点
func preNode(root *TreeNode) int {
for root.Right != nil {
root = root.Right
}
return root.Val
}
// 找右子树的最小节点
func postNode(root *TreeNode) int {
for root.Left != nil {
root = root.Left
}
return root.Val
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-03-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录