LeetCode 112 [Path Sum]

原题

给出一个二叉树和一个sum, 判断是否存在一条自根节点到叶节点路径，使路径和等于sum

样例
给出下面的二叉树 和 sum = 22

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

返回 True 因为5->4->11->2 的和等于22

解题思路

• 二叉树遍历
• 如果找到一个根到叶的路径求和，如果等于sum直接返回True

完整代码

# 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
        if self.helper(root, 0, sum) == True:
            return True
        return False
        
    def helper(self, root, subSum, sum):
        if root.left == None and root.right == None:
            if subSum + root.val == sum:
                return True
        if root.left and self.helper(root.left, subSum + root.val, sum):
            return True
        if root.right and self.helper(root.right, subSum + root.val, sum):
            return True