九章算法 | 亚马逊面试题：路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

在线评测地址: LintCode 领扣

样例 1:

        输入: root = {5,4,8,11,#,13,4,7,2,#,#,5,1}, sum = 22
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
输出: [[5,4,11,2],[5,8,4,5]]
解释:
两条路径之和为 22：
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
      

样例 2:

        输入: root = {10,6,7,5,2,1,8,#,9}, sum = 18
              10
             /  \
            6    7
          /  \   / \
          5  2   1  8
           \ 
            9 
输出: [[10,6,2],[10,7,1]]
解释:
两条路径之和为 18：
10 + 6 + 2 = 18
10 + 7 + 1 = 18
      

【题解】

当访问的节点是叶子节点的时候，新建一个列表，插入到result中，然后返回result。 分别遍历左右子树的节点，然后将他们分别插入到叶子节点之前。

        class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        # sum is overwriter, so new function my sum ....
        def mysum(nums):
            count = 0
            for n in nums:
                count += n
            return count
            
        # dfs find each path
        def findPath(root, path):
            if root.left is None and root.right is None:
                if mysum(path + [root.val]) == sum: 
                    allPath.append([t for t in path + [root.val]])
            
            if root.left: findPath(root.left, path + [root.val])
            if root.right: findPath(root.right, path + [root.val])
        
        
        allPath = []
        if root: findPath(root, [])
        return allPath
      

更多题解参见：九章算法