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的目标节点之间找到一条路径。正确的答案应该是[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的路由(。之后，您将调用DFS以获取右侧节点(3(。当你们使用相同堆栈的时间越长，为右边的节点调用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]