Path Sum*

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.

For example:

Given the below binary tree and

sum = 22

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

Solution:

asdfasdf首先我开始用了分治的思想，其实这道题不需要使用，分治算法的本质是把大问题划分成小问题，然后一路向下到最末级，然后把结果bubble up上来，这道题不需要，直接可以递归下去，把数值一路减下去，特殊的地方就是，需要知道等于0的那个节点，root.left == none and root.right == none

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root == None:
            return False
        sum -= root.val

        if root.left == None and root.right == None: #make sure it's reach the end of the path == 0
            return sum == 0

        if root.left and self.hasPathSum(root.left, sum):
            return True

        if root.right and self.hasPathSum(root.right, sum):
            return True

        return False