深度优先搜索只返回根值

Question

我正在尝试使用DFS获取树的值列表，但我只获取根的值。：(

def depthFirstSearch(root):
output = []
if root:
output.append(root.value)
depthFirstSearch(root.left)
depthFirstSearch(root.right)
return output

Answer 1

可能有点晚了，但如果你看看你所做的，只返回你的root是有道理的。

具体来说，在第一次迭代中附加root.value，然后为两个子项运行depthFirstSearch(大概在二叉树中(，但问题是：您只需丢弃结果。如果在返回之前将两个递归调用的结果连接到输出，则可能会起作用。

这会让你得到这样的东西：

def depthFirstSearch(root):
output = []
if root:
output.append(root.value)
# use the += operator to concatenate the current output list and the new one from the subtree
output += depthFirstSearch(root.left)
output += depthFirstSearch(root.right)
return output