二叉树中和为某一值的路径

题目描述

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

思路

这道题思路如下，先利用深度优先搜索的思路遍历整颗二叉树。返回的是一个二维数组，每一行可以看成一个完整的路径。
第二步是针对二维数组的每一行，求和计算，如果恰好等于目标数字，那么就是我们所求的路径。

代码

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        all_paths = self.binaryTreePath(root)
        result = []
        for i in range(len(all_paths)):
            current_sum = sum(all_paths[i])
            if current_sum == expectNumber:
                result.append(all_paths[i])
        return result

    def binaryTreePath(self,root):
        if not root:
            return []
        if not root.left and not root.right:
        #递归的出口，到达了叶子节点。
            return [[root.val]]
        result = []
        #以下是非叶子节点的处理，一方面是用递归向下搜索，另一方面是当递归从底层返回上来时，把当前的值加进去。
        if root.left:
            result += self.binaryTreePath(root.left)
        if root.right:
            result += self.binaryTreePath(root.right)
        for index  in range(len(result)):
            result[index].insert(0,root.val)
        return result