文章目录
1. 题目
给定一个二叉搜索树的根节点 root 和一个值 key ，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
1.1 示例
- 示例 1 1 1 ：
- 输入：
root = [5, 3, 6, 2, 4, null, 7]，key = 3；- 输出：
[5, 4, 6, 2, null, null, 7]；- 解释： 给定需要删除的节点值是 3 3 3 ，所以我们首先找到 3 3 3 这个节点，然后删除它。一个正确的答案是
[5, 4, 6, 2, null, null, 7]， 如下图所示。另一个正确答案是[5, 2, 6, null, 4, null, 7]。
- 示例 2 2 2 ：
- 输入：
root = [5, 3, 6, 2, 4, null, 7]，key = 0；- 输出：
[5, 3, 6, 2, 4, null, 7]；- 解释： 二叉树不包含值为 0 0 0 的节点。
1.2 说明
- 来源： 力扣（LeetCode）
- 链接： https://leetcode-cn.com/problems/delete-node-in-a-bst
1.3 限制
- 节点值唯一；
- 节点数的范围 [ 0 , 1 0 4 ] [0, 10^4] [0,104] ；
- − 1 0 5 < = key < = 1 0 5 -10^5 <= \text{key} <= 10^5 −105<=key<=105 ；
- − 1 0 5 < = Node.val < = 1 0 5 -10^5 <= \text{Node.val} <= 10^5 −105<=Node.val<=105 ；
-
root是合法的二叉搜索树的根节点。
1.4 进阶
要求算法时间复杂度为 O ( h ) O(h) O(h) ， h h h 为树的高度。
2. 解法一
- 作者： GeeksforGeeks
2.1 分析
删除二叉搜索树的节点时，第一步自然是要找到目标节点，这一步很简单，结合二叉搜索树的性质易知，如果令当前节点为 node ，则：
- 当
node.val > k时，目标节点在node的左子树中； - 当
node.val < k时，目标节点在node的右子树中； - 当
node.val == k时，执行对目标节点的删除操作。
本题的难点并不在于找到待删除的目标节点，而是如何删除目标节点，因为要保证删除目标节点之后得到的还是一棵二叉搜索树，具体可以分为三种情况来讨论：
- 目标节点为叶子节点，则直接执行删除目标节点的操作：
50 50
/ \ delete(20) / \
30 70 ---------> 30 70
/ \ / \ \ / \
20 40 60 80 40 60 80
- 目标节点仅有一个子节点，只要用子节点的
val覆盖目标节点的val，然后删除子节点即可：
50 50
/ \ delete(30) / \
30 70 ---------> 40 70
\ / \ / \
40 60 80 60 80
- 目标节点有两个子节点，此时需要先找到目标节点的后继节点，然后用后继节点的
val覆盖目标节点的val，最后删除后继节点1即可：
50 60
/ \ delete(50) / \
40 70 ---------> 40 70
/ \ \
60 80 80
需要注意的是，此时只有当目标节点的右子节点不为空，才需要目标节点的后继节点，此处定义了一个 protected 方法 _min_node 来寻找目标节点的后继节点，即将后继节点视为目标节点右子节点（子树） val 最小的节点。
2.2 实现
from typing import Optional, List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorder(self, root: TreeNode) -> List[int]:
if not isinstance(root, TreeNode):
return []
return self.inorder(root.left) + [root.val] + self.inorder(root.right)
def _min_node(self, node):
cursor = node
# loop down to find the leftmost leaf
while cursor.left is not None:
cursor = cursor.left
return cursor
def delete_node(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not isinstance(root, TreeNode):
return
# If the key to be deleted is smaller than the root's key then it lies in the left subtree
if key < root.val:
root.left = self.delete_node(root.left, key)
# If the key to be deleted is greater than the root's key then it lies in the right subtree
elif key > root.val:
root.right = self.delete_node(root.right, key)
# If key is the same as root's key, then this is the node to be deleted
else:
# Node with only one child or no child
if root.left is None:
child = root.right
return child
elif root.right is None:
child = root.left
return child
# Node with two children: Get the inorder successor (smallest in the right subtree)
successor = self._min_node(root.right)
# Copy the inorder successor's val attribute to this node
root.val = successor.val
# Delete the inorder successor
root.right = self.delete_node(root.right, successor.val)
return root
def main():
node7 = TreeNode(80)
node6 = TreeNode(60)
node5 = TreeNode(40)
node4 = TreeNode(20)
node3 = TreeNode(70, left=node6, right=node7)
node2 = TreeNode(30, left=node4, right=node5)
node1 = TreeNode(50, left=node2, right=node3)
root = node1
sln = Solution()
print('inorder:', sln.inorder(root)) # inorder: [20, 30, 40, 50, 60, 70, 80]
sln.delete_node(root, 20)
print('inorder:', sln.inorder(root)) # inorder: [30, 40, 50, 60, 70, 80]
sln.delete_node(root, 30)
print('inorder:', sln.inorder(root)) # inorder: [40, 50, 60, 70, 80]
sln.delete_node(root, 50)
print('inorder:', sln.inorder(root)) # inorder: [40, 60, 70, 80]
sln.delete_node(root, 90)
print('inorder:', sln.inorder(root)) # inorder: [40, 60, 70, 80]
if __name__ == '__main__':
main()
2.3 复杂度
- 时间复杂度： O ( n ) O(n) O(n) ，最坏情况下二叉搜索树呈链状，此时若删除叶子节点，则每个节点都会被遍历到；
- 空间复杂度： O ( n ) O(n) O(n) ，最坏情况下二叉搜索树呈链状，此时递归调用的深度为 O ( n ) O(n) O(n) ，即维持递归的隐式开销和深度成正相关。
-
这里也可以使用前驱节点。 ↩︎