OneCoder Avatar
OneCodercoderli.com · 1025 篇博文
🧮 Algo

数据结构与算法

🎨 视觉封面

LeetCode Path Sum

📅 2017-11-27·✍️ onecode·计算中...·⏱️ 4 分钟

Problem

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,

Code7 行
             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.

Python5 行
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Python 实现

Python37 行

'''
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.
'''
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root == None:
            return False
        leftValue = sum - root.val
        if root.left == None and root.right == None and leftValue == 0:
            return True
        return self.hasPathSum(root.left, leftValue) or self.hasPathSum(root.right, leftValue)

分析

还是递归的思路。子树有满足减去当前节点值的和即可。

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!