112、Path Sum

可以按照前序遍历的顺序遍历树，在遍历过程中，定义一个变量，
这个变量等于sum减去已经被遍历过的所有节点的val。一直到叶节点时，若是这个叶节点等于这个sum，就说明书中存在这样一个路径。

树的遍历，想到了递归函数，于是调用递归函数。

• 递归结束条件：
  1、节点为None，则返回False。
  2、为叶节点时（左右节点为空）并且叶节点等于传入的sum时，返回True。
  （3、为叶节点但是sum不等于val时，此时在递归调用左右子树时，也可以代替了，因此不用写了）

• 递归改变的条件，sum每次都会减去node的val，不断减小

• 递归调用，在节点不为叶节点的时候，调用函数
  注意在最后对左右子节点调用函数时，有一个为True，就满足题意了。所以应该用“or”语句连接两个递归函数。

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

class Solution:
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """

        if root == None:
            return False
        if root.left == None and root.right == None and root.val == sum:
            return True
        #有一个为正确的，那就是正确
        return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)