Path Sum II*

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and

sum = 22

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

return

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

Solution:

sdfs求所有路行，需要对二叉树做DFS，这个时候需要注意的就是这个level变量，这个是running的变量，所以当返回上一个级别的时候需要清空。

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if root == None:
            return []
        result = []
        self.dfs(root, sum, result, [])
        return result
    def dfs(self, root, sum, result, level):
        if root == None:
            return
        sum -= root.val
        level.append(root.val)

        if root.left == None and root.right == None:
            if sum == 0:
                result.append(list(level))
        if root.left:
            self.dfs(root.left, sum, result, level)
            del level[-1]
        if root.right:
            self.dfs(root.right, sum, result, level)
            del level[-1]