LeetCode 112. Path Sum 20170705 部分之前做了没写的题目

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

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

题目大意：给定一个二叉树和一个总和，问是否存在一个从根节点到叶节点的路径使该路径的和等于所给的总和。

解题思路：该题可以用递归的方法，遍历整棵树，从根节点开始，往下走，每走一步，都把sum减掉父节点的值，如果走到了叶子节点的位置，也就是该节点没有左子节点也没有右子节点，则判断当前的sum跟叶子节点上的值是否相当。如果相等，则说明该沿着该路径从根节点走到该叶子节点上所有节点的值的和等于sum。由于只要有任意一条路径的和等于sum就返回true，所以在递归时采用左子树or右子树的方式。

class Solution(object):
　　def hasPathSum(self, root, sum):
　　　　if root == None:
　　　　　　return False
　　　　elif root.left == None and root.right == None:
　　　　　　if root.val == sum:
　　　　　　　　return True
　　　　　　else:
　　　　　　　　return False
　　　　else:
　　　　　　return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)