Path Sum

这题是比较少见的二叉树里面不太好用分治法做的题目，此题最好的方法还是传参到底也就是DFS一路往下搜索答案

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False

        if not root.left and not root.right:
            return (sum - root.val) == 0

        sum -= root.val

        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

Path Sum II

稍微有点像回溯，但是总体逻辑和上题一样

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        tmp, res = [], []
        self.helper(root, sum, tmp, res)
        return res

    def helper(self, root, sum, tmp, res):
        if not root:
            return 

        if not root.left and not root.right and root.val == sum:
            tmp.append(root.val)
            res.append(tmp[:])
            tmp.pop()
            return

        tmp.append(root.val)
        self.helper(root.left, sum - root.val, tmp, res)
        self.helper(root.right, sum - root.val, tmp, res)
        tmp.pop()