我正在尝试解决 GeeksforGeeks 问题 从 BST 中删除节点 :
给定一棵二叉搜索树和一个节点值X。从BST中删除具有给定值X的节点。如果不存在值为 x 的节点,则不要进行任何更改。
示例1:
Input: 2 / \ 1 3 X = 12
输出: 1 2 3
解释: 在给定的输入中 没有值为 12 的节点,因此树 将保持不变。
您的任务:
您不需要读取输入或打印任何内容。你的任务是完成带有两个参数的函数
。第一个是树的
deleteNode()
,整数root
表示要从 BST 中删除的节点值。删除值为 X 的节点后返回 BST 的根。如果 BST 中不存在值为 X 的节点,则不进行任何更新。X
看到解决方案后,我尝试自己编写解决方案。
这是我的尝试:
def getSuccessor(node):
node = node.right
while node and node.left:
node = node.left
return node.data
#Function to delete a node from BST.
def deleteNode(root, X):
# code here.
if root is None:
return root
elif root.data>X:
root.left = deleteNode(root.left,X)
elif root.data<X:
root.right = deleteNode(root.right,X)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
else:
root.data = getSuccessor(root)
# print(root.data)
root.right = deleteNode(root.right,root.data)
return root
这是我在尝试自己之前查找过的可行解决方案:
#User function Template for python3
def getSuccessor(node):
node = node.right
while node and node.left:
node = node.left
return node
def deleteNode(root, X):
if root is None:
return root
elif root.data > X:
root.left = deleteNode(root.left, X)
elif root.data < X:
root.right = deleteNode(root.right, X)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
else:
temp = getSuccessor(root)
root.data = temp.data
root.right = deleteNode(root.right, temp.data)
return root
我只更改了上面的
getSuccessor
功能,因为我只需要 node.data
。但这不起作用。我认为这与 Python 通过引用传递对象有关,但我不明白如何实现?
我尝试更改解决方案,但无法使其工作。对于第一个测试用例(见上文),它什么也没输出,而树 1 2 3 是预期的。
我只改变了上面的
功能getSuccessor
还有更多差异。您已经移动了最后一个
return root
,因此现在有些情况下您的函数不执行 return
语句,而是返回 None
。
这应该很容易发现。解决方法是将
return root
语句准确放置在工作版本中的位置,即具有相同的缩进。