LeetCode 113 [Path Sum II]

原题

给出一个二叉树和一个sum, 找出所有存在的自根节点到叶节点的路径，如果路径和等于sum

样例
给出如下二叉树和 sum = 22

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回

[
   [5,4,11,2],
   [5,8,4,5]
]

解题思路

• 二叉树遍历
• helper函数要保存subSum, path，当节点为根节点而且和等于sum时，向res中添加此刻的path

完整代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        res = []
        if not root:
            return res
        self.helper(root, [], 0, sum, res)
        return res
        
    def helper(self, root, path, subSum, sum, res):
        if root.left == None and root.right == None:
            if subSum + root.val == sum:
                res.append(path + [root.val])
        if root.left:
            self.helper(root.left, path + [root.val], subSum + root.val, sum, res)
        if root.right:
            self.helper(root.right, path + [root.val], subSum + root.val, sum, res)