0112. 路径总和

0112. 路径总和 #

  • 标签:树、深度优先搜索
  • 难度:简单

题目大意 #

给定一个二叉树 和一个值 targetSum,判断该树中是否存在从根节点到叶子节点的路径,使得这条路径上所有节点值相加等于 targetSum。

解题思路 #

递归求解。新增一个变量 currSum,表示为从根节点到当前节点的路径上所有节点值之和。递归遍历左右子树,同时更新维护 currSum 值。

当当前节点为叶子节点时,判断 currSum 是否与 targetSum 相等,否则继续遍历左右子树。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        return self.sum(root, targetSum, 0)

    def sum(self, root: TreeNode, targetSum: int, curSum:int) -> bool:
        if root == None:
            return False
        curSum += root.val
        if root.left == None and root.right == None:
            return curSum == targetSum
        else:
            return self.sum(root.left, targetSum, curSum) or self.sum(root.right, targetSum, curSum)
本站总访问量  次  |  您是本站第  位访问者