【python-leetcode112-树的深度遍历】路径总和

发布时间：2020-12-20 09:54:06 所属栏目：Python 来源：网络整理

导读：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明:?叶子节点是指没有子节点的节点。示例:? 给定如下二叉树，以及目标和 sum = 22， ? ? ?5 ? ?/? ? ?4? ? ? 8 ?/? ? ? ?/ 11? 13 4 /

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

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

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

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

# 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
         self.helper(root,sum)
    def helper(self,root,cur,sum):
        计算当前路径的值
        cur+=root.val
        当遍历到叶子节点时进行判断
        if root.left == None and root.right == None:
            return cur == sum
        否则继续遍历
        return self.helper(root.left,sum) or self.helper(root.right,sum)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!