欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 112 [Path Sum]

程序员文章站 2024-01-05 11:41:10
...

原题

给出一个二叉树和一个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

上一篇:

下一篇: