前言
新的一年，好好学习。尝试用python写写代码。
正文
问题来源
本问题来自leetcode上的112题。
问题描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
分析：
递归版本
本来第一反应在Solution类中添加一个成员记录总路程，递归调用时回退走过的路径。
后来想了想根本不需要这么麻烦，直接传入临时参数，就不需要回退操作。
# 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
"""
if not root:
return False
return self.existPathSum(root, sum)
def existPathSum(self, root, sum):
ret = False
if None == root.left and None == root.right:
if sum - root.val == 0:
return True
else: return False
if None != root.left:
ret = ret or self.hasPathSum(root.left, sum-root.val)
if None != root.right:
ret = ret or self.hasPathSum(root.right, sum-root.val)
return ret
在判断右节点前可以判断ret是否已经为True（剪枝优化）。写代码的时候没有想到这么一个点。
递归版（别人）
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
return (self.hasPathSum(root.left, sum - root.val)) or (self.hasPathSum(root.right, sum - root.val))
将左右子树作为参数传入递归调用前，不进行判None，效率比判断None快，这个是我没有想到的。
总结：
勤思考。
结语
不管怎么样好好加油。
