[112] Path Sum

https://leetcode.com/problems/path-sum/description/

• algorithms
• Easy (36.29%)
• Source Code: 112.path-sum.py
• Total Accepted: 301.9K
• Total Submissions: 805.9K
• Testcase Example: '[5,4,8,11,null,13,4,7,2,null,null,null,1]\n22'

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

  5
 / \
4   8

/ /
11 13 4 / \
7 2 1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

# 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 hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        paths = []
        self.travel_path(root, paths, [])
        for p in paths:
            if reduce(lambda a, b: a+b, p) == sum: return True

        return False

    def travel_path(self, root, paths, current):
        if not root: return

        current = current[:]
        current.append(root.val)
        if not root.left and not root.right:
            paths.append(current)
            return
        else:
            if root.left:
                self.travel_path(root.left, paths, current)
            if root.right:
                self.travel_path(root.right, paths, current)