DFS实现在两个树节点之间查找路由

Question

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def getDFSpath(root,goal,stack):
    stack.append(root.val)
    if root.left is None and root.right is None and root.val != goal:
        stack.pop()
        return []
    elif root.val == goal:
        return stack
    else:
        leftstack = getDFSpath(root.left,goal,stack)
        rightstack = getDFSpath(root.right,goal,stack)
        if len(leftstack) == 0 and len(rightstack) > 0:
            return rightstack
        elif len(rightstack) == 0 and len(leftstack) > 0:
            return leftstack
        else:
            return []

one = TreeNode(1)
two =TreeNode(2)
three =TreeNode(3)
four = TreeNode(4)
five =TreeNode(5)
six =TreeNode(6)
seven =TreeNode(7)
eight = TreeNode(8)
nine =TreeNode(9)
ten = TreeNode(10)
eleven = TreeNode(11)

one.left = two
one.right = three
two.left = four
two.right = five
three.left = six
three.right = seven
four.left = ten
four.right = eleven
five.left = nine
five.right = eight
mystack = getDFSpath(one,11,[])
print(mystack)

我不确定此实现有什么问题。我试图在节点1和目标节点之间找到一条值为11的路线。正确的ans应该为[1,2,4,11]。但是它返回了：[1、2、4、11、5、3]

Answer 1

让我们仔细看一下下面的代码行：

leftstack = getDFSpath(root.left,goal,stack)
rightstack = getDFSpath(root.right,goal,stack)

这里您为左节点和右节点都调用DFS，并传递相同的stack变量。例如，为左节点调用DFS会找到一条路径（简单示例-从1到2的路由）。之后，为右节点（3）调用DFS。只要您使用相同的堆栈变量，为正确的节点调用DFS，就会对其进行修改。看下面的行：

if root.left is None and root.right is None and root.val != goal:

对于节点3，这不是真的，因此它不会从堆栈中删除3！结果是[1, 2, 3]。同样，当节点只有左孩子或只有右孩子时，您将无法处理这种情况。带有我的评论的固定代码：

def getDFSpath(root, goal, stack):
    stack.append(root.val)
    if root.val == goal:
        return stack
    else:
        leftstack = getDFSpath(root.left, goal, stack[:]) if root.left is not None else []  # if left node is missing skip it
        rightstack = getDFSpath(root.right, goal, stack[:]) if root.right is not None else []  # if right node is missing skip it
        if len(leftstack) == 0 and len(rightstack) > 0:
            return rightstack
        elif len(rightstack) == 0 and len(leftstack) > 0:
            return leftstack
        else:
            stack.pop()  # we didn't find path, remove current node from stack
            return []

输出：

[1、2、4、11]