112. Path Sum [easy] (Python)

该博客探讨了如何解决LeetCode中的'Path Sum'问题,即判断二叉树是否存在一条从根到叶节点的路径,使得路径上的节点值之和等于给定的目标值。文章提供了四种解法,包括深度优先搜索(DFS)的递归和非递归实现,广度优先搜索(BFS)以及后序遍历的方法,并附有相应的Python代码示例。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

题目链接

https://leetcode.com/problems/path-sum/

题目原文

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.

题目翻译

给定一个二叉树及一个和数sum,判断这个树是否有一条从根到叶的路径,这条路径上所有数之和为sum。比如,给定sum=22,二叉树为:

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

那么应该返回true,因为存在路径 5->4->11->2 ,其和为22。

思路方法

思路一

用深度优先搜索(DFS)遍历所有可能的从根到叶的路径,要注意每深一层要从和中减去相应节点的数值。下面是递归实现的代码。

代码

# 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 not root.left and not root.right:
            return True if sum == root.val else False
        else:
            return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

思路二

DFS的非递归实现,用栈实现。

代码

# 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
        """
        stack = [(root, sum)]
        while len(stack) > 0:
            node, tmp_sum = stack.pop()
            if node:
                if not node.left and not node.right and node.val == tmp_sum:
                    return True
                stack.append((node.right, tmp_sum-node.val))
                stack.append((node.left, tmp_sum-node.val))
        return False

思路三

BFS方法,用队列实现。

代码

# 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
        """
        queue = [(root, sum)]
        while len(queue) > 0:
            node, tmp_sum = queue.pop()
            if node:
                if not node.left and not node.right and node.val == tmp_sum:
                    return True
                queue.insert(0, (node.right, tmp_sum-node.val))
                queue.insert(0, (node.left, tmp_sum-node.val))
        return False

思路四

如果说上面都是比较常规的方法,那么后序遍历算是比较新奇的解法了。虽然也用的栈,但后序遍历的一大好处是它直接将路径保存在栈中,每次进入不同的层不需要记录当前的和。算是与DFS各有所长吧。

代码

# 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
        """
        pre, cur = None, root
        tmp_sum = 0
        stack = []
        while cur or len(stack) > 0:
            while cur:
                stack.append(cur)
                tmp_sum += cur.val
                cur = cur.left
            cur = stack[-1]
            if not cur.left and not cur.right and tmp_sum == sum:
                return True
            if cur.right and pre != cur.right:
                cur = cur.right
            else:
                pre = cur
                stack.pop()
                tmp_sum -= cur.val
                cur = None
        return False

PS: 新手刷LeetCode,新手写博客,写错了或者写的不清楚还请帮忙指出,谢谢!
转载请注明:http://blog.csdn.net/coder_orz/article/details/51595815

### 关于LeetCode Python 150道题目实践 在准备技术面试的过程中,解决编程问题是提升技能的重要方式之一。对于Python开发者而言,在LeetCode平台上完成一系列经典问题可以帮助巩固基础知识并提高解决问题的能力。以下是关于如何高效利用LeetCode平台以及推荐的150道Python相关题目列表。 #### 高效使用LeetCode的方法 尽管提到LeetCode存在一些局限性[^1],比如缺乏对代码可读性和变量命名的要求,但它仍然是学习算法和数据结构的有效工具。为了弥补这些不足之处,可以采取以下策略: - **注重代码质量**:即使LeetCode不强制执行良好的编码习惯,也应主动优化自己的代码风格,包括清晰的变量名、合理的函数拆分等。 - **深入分析解法**:每次提交解答之后,尝试思考是否有更优的时间复杂度或者空间复杂度改进方案,并研究其他用户的高赞答案以获取灵感。 - **模拟真实场景**:通过自行设计扩展需求来增强原题目的挑战程度,从而锻炼应对实际工作中可能出现的变化情况。 #### 推荐的150道Python题目分类 下面按照难度等级划分了一些适合初学者到高级程序员练习的经典习题: ##### 易 (Easy Level) ```plaintext 1. Two Sum 2. Reverse Integer ... (共约40道简单级别题目省略显示) ``` ##### 中等 (Medium Level) ```plaintext 41. First Missing Positive 42. Trapping Rain Water ... (大约70道中等等级题目同样仅列举部分名称如下:) 88. Merge Sorted Array 94. Binary Tree Inorder Traversal ... ``` ##### 困难 (Hard Level) ```plaintext 114. Flatten Binary Tree to Linked List 124. Binary Tree Maximum Path Sum ... (最后大概有40道较难题目举例说明其中几个:) 239. Sliding Window Maximum 264. Ugly Number II ... ``` 由于篇幅原因无法逐一列出全部具体编号与描述,请访问官方网站筛选标签为`Python`的相关条目即可找到完整的清单链接地址[^2]. #### 示例代码片段展示 这里给出一道常见入门级别的例子——两数之和(Two Sum),附带简洁易懂实现版本供参考: ```python def twoSum(nums, target): num_to_index = {} for i, num in enumerate(nums): complement = target - num if complement in num_to_index: return [num_to_index[complement], i] num_to_index[num] = i raise ValueError("No solution found.") ``` 此方法采用哈希表记录已遍历过的数值及其索引位置关系,能够显著降低时间消耗至O(n)水平[^3]. ---
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值