题目

https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
image.png

思路

深度优先搜索

在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。以数组{5,7,6,9,11,10,8}为例，后序遍历结果的最后一个数字8就是根结点的值。在这个数组中，前3个数字5、7和6都比8小，是值为8的结点的左子树结点；后3个数字9、11和10都比8大，是值为8的结点的右子树结点。我们接下来用同样的方法确定与数组每一部分对应的子树的结构。这其实就是一个递归的过程。对于序列5、7、6，最后一个数字6是左子树的根结点的值。数字5比6小，是值为6的结点的左子结点，而7则是它的右子结点。同样，在序列9、11、10中，最后一个数字10是右子树的根结点，数字9比10小，是值为10的结点的左子结点，而11则是它的右子结点。我们再来分析另一个整数数组{7,4,6,5}。后序遍历的最后一个数是根结点，因此根结点的值是5。由于第一个数字7大于5，因此在对应的二叉搜索树中，根结点上是没有左子树的，数字7、4和6都是右子树结点的值。但我们发现在右子树中有一个结点的值是4，比根结点的值5小，这违背了二叉搜索树的定义。因此不存在一棵二叉搜索树，它的后序遍历的结果是7、4、6、5。

代码

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
  10.         ans, path = [], []
  11.         def dfs(node, sum):
  12.             if not node:
  13.                 return
  14.             else:
  15.                 path.append(node.val)
  16.                 sum -= node.val
  18.             # 判断其是叶子节点和 path==sum
  19.             if not node.left and not node.right and not sum:
  20.                 ans.append(path.copy())
  22.             dfs(node.left, sum)
  23.             dfs(node.right, sum)
  24.             path.pop()
  26.         dfs(root, sum)
  28.         return ans

注意：path是一个对象，python一切皆对象，如果不进行拷贝（copy，或者path[:]），那么最好path.pop()会将path清空。