LeetCode-112 路径总和 --- Python代码实现及详解

朱雀 2020-10-31 18:27 583阅读 0赞

### 题目： ###

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

说明: 叶子节点是指没有子节点的节点。

示例:

给定如下二叉树，以及目标和 sum = 22，

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

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

### 思路： ###

利用减法思想只要sum-root.val等于0，就说明有路径总和等于目标值。从根节点开始用sum-root.val值与0进行比较，如果相等说明有路径总和等于目标值直接返回true，如果不相等重复以上步骤分别递归左节点和右节点。该题利用先根遍历思想进行改变。

### 编码实现： ###

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

时间复杂度：我们访问每个节点一次，时间复杂度为 O(N)，其中 N是节点个数。

发表评论取消回复

表情：

评论列表（有 0 条评论，583人围观）

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

相关阅读

相关 leetcode 112路径总和

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

客官°小女子只卖身不卖艺/ 2023年06月18日 05:57/ 0 赞/ 68 阅读

相关 112. 路径总和

题目来源 [112. 路径总和][112.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shado

末蓝、/ 2022年12月19日 11:49/ 0 赞/ 113 阅读

相关 leetcode算法【112】路径总和

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

迷南。/ 2022年11月26日 07:38/ 0 赞/ 115 阅读

相关 leetcode 112. 路径总和(python)

【前言】 python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/

╰半橙微兮°/ 2022年05月19日 10:27/ 0 赞/ 164 阅读

相关 LeetCode112. 路径总和

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

我会带着你远行/ 2022年05月09日 07:38/ 0 赞/ 149 阅读

相关 leetcode 112. 路径总和(java)

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

Love The Way You Lie/ 2022年04月15日 07:14/ 0 赞/ 130 阅读

相关路径总和【 leetcode - 112 - 简单】

胡扯：这个题的确见证了我的进步，连续刷了几天的dfs了，从开始的不知如何下手，到这个一次提交以打败 100% 通过，开心。 ![watermark_type

骑猪看日落/ 2022年04月10日 13:09/ 0 赞/ 181 阅读

相关 112. 路径总和

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

旧城等待，/ 2022年01月07日 14:51/ 0 赞/ 346 阅读

相关 LeetCode第112题：路径总和

1. 题目：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在根节点到叶子节点的路径，这条路径上所

﹏ヽ暗。殇╰゛Y/ 2021年09月21日 17:20/ 0 赞/ 247 阅读

相关 LeetCode-112 路径总和 --- Python代码实现及详解

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

朱雀/ 2020年10月31日 18:27/ 0 赞/ 584 阅读