从 BST 中删除节点失败，结果为空——但我的代码基于工作解决方案代码 [已关闭]

Question

我正在尝试解决 GeeksforGeeks 问题 从 BST 中删除节点 ：

给定一棵二叉搜索树和一个节点值X。从BST中删除具有给定值X的节点。如果不存在值为 x 的节点，则不要进行任何更改。

示例1：

Input:
      2
    /   \
   1     3
X = 12

输出： 1 2 3

解释： 在给定的输入中 没有值为 12 的节点，因此树 将保持不变。

您的任务：

您不需要读取输入或打印任何内容。你的任务是完成带有两个参数的函数

deleteNode()

。第一个是树的

root

，整数

X

表示要从 BST 中删除的节点值。删除值为 X 的节点后返回 BST 的根。如果 BST 中不存在值为 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 是预期的。

Answer 1

我只改变了上面的

getSuccessor

功能

还有更多差异。您已经移动了最后一个

return root

，因此现在有些情况下您的函数不执行

return

语句，而是返回

None

。

这应该很容易发现。解决方法是将

return root

语句准确放置在工作版本中的位置，即具有相同的缩进。