题解 | #二叉树中和为某一值的路径(一)#

二叉树中和为某一值的路径(一)

https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c

from enum import Flag
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return bool布尔型
#
class Solution:
    def hasPathSum(self , root: TreeNode, s: int) -> bool:
        # write code here
        res = [] # 尝试用更少的空间
        if not root:
            return False
        flag = [False]
        def backtrace(root): # 递归搜索
            res.append(root.val)
            if not root.left and not root.right: # 如果搜到叶子节点
                if sum(res) == s: # 判断和等不等
                    flag=True
                    return
            if root.left:
                backtrace(root.left) # 左递归
                if not flag[0]:
                    res.pop() # 回溯
                else:
                    return
            if root.right:
                backtrace(root.right) # 右递归
                if not flag[0]:
                    res.pop() # 回溯
                else:
                    return

        backtrace(root)
        return flag[0]





        ''' # 以下是两个栈的O(n)复杂度解法
        if not root:
            return False
        from collections import deque
        DQ = deque([root])
        PATH = deque([[root.val]])

        while DQ:
            cur = DQ.popleft()
            cur_path = PATH.popleft()
            if sum(cur_path) == s and not cur.left and not cur.right:
                return True
            if cur.left:
                DQ.append(cur.left)
                PATH.append(cur_path + [cur.left.val])
            if cur.right:
                DQ.append(cur.right)
                PATH.append(cur_path + [cur.right.val])

        return False
        '''

全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务