[Leetcode][python]Path Sum/路径总和

不念不忘少年蓝@ 2022-06-11 09:25 288阅读 0赞

题目大意

给定一个数和一棵树，求能否有一条路径上所有叶子结点数值加起来等于给定的数

解题思路

递归

代码

  1. class Solution(object):
  2.     def hasPathSum(self, root, sum):
  3.         """
  4.         :type root: TreeNode
  5.         :type sum: int
  6.         :rtype: bool
  7.         """
  8.         if root == None:
  9.             return False
  10.         if root.left == None and root.right == None:
  11.             return sum == root.val
  12.         return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

总结

  • 题目要求的和必须是一直贯穿到最下面的叶子结点。不需要考虑中间就到达和的情况

  • 这种题目的递归结构都十分相似，通过这种结构来遍历到整个树。

    self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

发表评论

表情：
评论列表 （有 0 条评论，288人围观）

还没有评论，来说两句吧...

相关阅读

    相关 LeetCode 112.Path Sum (路径总和)

    题目描述： 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:

    怼烎@怼烎@/ 0 赞/ 337 阅读