查找二叉树中的所有路径

Question

我正在尝试解决"给定二叉树，返回所有根到叶路径"的编码问题。

Input:
1
/   
2     3

5
Output: ["1->2->5", "1->3"]

我看到了一个解决方案

class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
allPath = []
if root is None:
return []
self.find_all_paths_recursive(root, [], allPath)
return allPath
def find_all_paths_recursive(self, currNode, currPath, allPath):
if currNode is None:
return 
currPath.append(currNode.val)
if currNode.left is None and currNode.right is None:
currOut = '->'.join([str(x) for x in list(currPath)])
allPath.append(currOut)
# traverse left sub tree
self.find_all_paths_recursive(currNode.left, currPath, allPath)
# traverse right sub tree
self.find_all_paths_recursive(currNode.right, currPath, allPath)
del currPath[-1]

运行上面的代码给了我["1->2->5"，"1->3"]的答案，这是正确的。

我在想通过将if currNode.left is None and currNode.right is None:下的代码块更改为

if currNode.left is None and currNode.right is None:
#currOut = '->'.join([str(x) for x in list(currPath)])
#allPath.append(currOut)
allPath.append(currPath)

应该给我结果[[1,2,5]，[1,3]]。但是，此更改向我返回了结果 [[]，[]]。我想知道为什么这不起作用？

Answer 1

由于您要直接添加currPath，因此您必须在此时添加currPath的副本。

喜欢这个：

if currNode.left is None and currNode.right is None:
#currOut = '->'.join([str(x) for x in list(currPath)])
# allPath.append(currOut)
allPath.append(list(currPath))

编辑：

如果不添加list则将原始列表对象添加到 allPath，该对象将因递归而更新。添加list将创建一个copy of the original list object，该将被保存，不再进一步更新。

Answer 2

递归是一种函数式遗产，因此将其与函数式风格一起使用会产生最佳结果。这意味着避免事物变量重新分配、其他突变和副作用。

让我们看看以这种方式实现btree会是什么样子。请注意，构造新节点时可以设置left和rightnode属性 -

# btree.py
def empty():
return None
class node:
def __init__(self, val, left = empty(), right = empty()):
self.val = val
self.left = left
self.right = right
def paths(t, p = ()):
if not t:
return
elif t.left or t.right:
yield from paths(t.left, (*p, t.val))
yield from paths(t.right, (*p, t.val))
else:
yield "->".join(map(str, (*p, t.val)))

这是您现在main程序 -

# main.py
from btree import node, empty, paths
#    1
#  /   
# 2     3
#  
#   5
t = node(1, node(2, empty(), node(5)), node(3))
print(list(paths(t)))

['1->2->5', '1->3']