题解 | #二叉树根节点到叶子节点和为指定值的路径#

递归搜索,搜索到空树直接返回,如果不是空树,判断是否为叶子节点,

1. 如果是:

• 再判断路径求和是否满足要求,满足的话将路径并入保存答案的list中
• 不满足直接返回

2. 如果不是:

• 将对应值与之前的路径拼接,作为新路径,继续遍历子节点

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return int整型二维数组
#
class Solution:
    def pathSum(self , root , sum ):
        # write code here
        L =[]
        prelist=[]
        def df(root,presum,prelist):
            if not root:
                return None
            newlist=prelist[:]
            newlist.append(root.val)
            if not root.left and not root.right:
                if presum+root.val==sum:
                    L.append(newlist)
            df(root.left,presum+root.val,newlist)
            df(root.right,presum+root.val,newlist)
        df(root=root,presum=0,prelist=prelist)
        return L