Path Sum

题目

给予一个二叉树，和一个值su，寻找是否有一个从根节点到叶节点的和为su，有则返回True，没有为False。比如：

          5

         / \

        4   8

       /   / \

      11  13  4

     /  \      \

    7    2      1

hasPathSum(self, root, 22) 将返回True

节点为：

class TreeNode:

   def __init__(self, x):

      self.val = x

      self.left = None

      self.right = None

解题思路

class Solution:

    # @param {TreeNode} root

    # @param {integer} sum

    # @return {boolean}

    def hasPathSum(self, root, su):

        flag = False

        if not root:

            return flag

        su -= root.val

        if su == 0 and (not root.left) and (not root.right):

            flag = True

        return flag or self.hasPathSum(root.left, su) or self.hasPathSum(root.right, su)