打印二叉树(DFS)的所有路径
问题描述:
我试图打印二叉树的所有路径(根到叶路径),但无济于事。打印二叉树(DFS)的所有路径
我的策略是使用递归,其基本情况为either tree is None or tree node is leaf return
否则,遍历树的左侧和右侧。
但我找不到保留左右树的方法。
def pathSum(self, root, target, result):
if not root:
return []
if not root.left and not root.right:
return [root.val]
for i in [root.left, root.right]:
path = [root.val] + self.pathSum(i, target, result)
print("path", path)
return path
答
的想法在每个节点访问正在建设的路径(列表),如果当前节点是叶,增加电流路径,并打印出来,如果没有,只是增加电流扩展的路径:
def pathSum(self, path):
if not self.left and not self.right:
print(path + [self.val])
return
self.left.pathSum(path + [self.val])
self.right.pathSum(path + [self.val])
root.pathSum([])
更新:如果你想保留的所有路径:
def pathSum(self, current_path, all_paths):
if not self.left and not self.right:
print('Path found: ' + str(current_path + [self.val]))
all_paths.append(current_path + [self.val])
return
self.left.pathSum(current_path + [self.val], all_paths)
self.right.pathSum(current_path + [self.val], all_paths)
all_paths = []
root.pathSum([], all_paths)
print('All paths: ' + str(all_paths))
答
通过一些迭代,我发现下面的解决方案工作。但我不确定是否有更有效的方法来查找所有叶根路径。
这一解决方案背后的想法是前序遍历
def allPaths(self, root, path, all_path):
if not root.left and not root.right:
path.append(root.val)
all_path.append(path[:])
return
if root:
path.append(root.val)
self.allPaths(root.left, path, all_path)
path.pop(-1)
self.allPaths(root.right, path, all_path)
path.pop(-1)
return all_path
+0
我再次检查。该解决方案仍然是错误的。作为'''path.pop(-1)''''一旦它回溯到树的根,就删除了根节点。 – jen007
请定义一个“路径” - 它是一个树的遍历,或从根到叶的路径? –
一个路径是一个根叶路径 – jen007
我认为这应该是非常类似于预购遍历 – jen007