删除二叉排序树节点时,如果节点有两个孩子,则横线上应填入(),其中findMax和findMin分别为找树的最大值和最小值。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def find_min(node):
"""在二叉搜索树中找到最小节点"""
current = node
while current and current.left:
current = current.left
return current
def delete_node(root, key):
if not root:
return None
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
else:
temp = find_min(_________) # 找到右子树中的最小节点
root.val = temp.val
root.right = delete_node(root.right, temp.val)
return root