题目标题

输入一颗二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。

难度:中级

数据分析
参考解析

coding=utf-8

“””
question:
输入一颗二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。
路径定义为从树的根节点开始往下一直到叶节点所经过的节点所形成的路径。
“””

节点类

class TreeNode:
def init(self, val):
self.val = val
self.left_child = None
self.right_child = None

在根节点为 root 的树中寻找和为 n 的路径

def find_sum_path(root, n):
ret = [] # 答案路径列表

  1. # 在根节点为 root 的树中寻找和为 n 的路径,以前的路径为 path
  2. # 这里讨论的算法是树的所有节点的值都是正数
  3. def find_path(root, path, n):
  4. path.append(root.val) # 当前节点加入路径
  5. if root.val > n: # 节点值已经大于 n,无解,若考虑负数,此分支不应存在
  6. pass
  7. elif root.val == n and root.left_child is None and root.right_child is None: # 解路径
  8. ret.append(path.copy())
  9. else:
  10. if root.left_child: # 遍历左子树
  11. find_path(root.left_child, path, n - root.val)
  12. if root.right_child: # 遍历右子树
  13. find_path(root.right_child, path, n - root.val)
  14. path.pop() # 当前节点从路径删除
  15. find_path(root, [], n)
  16. return ret

if name == ‘main‘:

  1. # 构造一棵树
  2. """
  3. 10
  4. 6 15
  5. 11 20
  6. 9
  7. """
  8. l = [6, 9, 10, 11, 15, 20]
  9. t = []
  10. for i in l:
  11. t.append(TreeNode(i))
  12. t[2].left_child = t[0]
  13. t[2].right_child = t[4]
  14. t[4].left_child = t[3]
  15. t[4].right_child = t[5]
  16. t[3].left_child = t[1]
  17. # 测试
  18. print(find_sum_path(t[2], 36))
  19. print(find_sum_path(t[2], 16))
  20. print(find_sum_path(t[2], 45))