程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

暂无数据

Leetcode 1161.最大层内元素和(Maximum Level Sum of a Binary Tree)

发布于2020-03-13 12:53     阅读(1030)     评论(0)     点赞(28)     收藏(0)


Leetcode 1161.最大层内元素和

1 题目描述(Leetcode题目链接

  给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层,而根节点的子节点位于第 2 层,依此类推。
  请你找出层内元素之和 最大 的那几层(可能只有一层)的层号,并返回其中 最小 的那个。

在这里插入图片描述

输入:[1,7,0,7,-8,null,null]
输出:2
解释:
第 1 层各元素之和为 1,
第 2 层各元素之和为 7 + 0 = 7,
第 3 层各元素之和为 7 + -8 = -1,
所以我们返回第 2 层的层号,它的层内元素之和最大。

提示:

  • 树中的节点数介于 1 和 104 10^4 之间
  • 105<=node.val<=105 -10^5 <= node.val <= 10^5

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 maxLevelSum(self, root: TreeNode) -> int:
        queue = collections.deque([root])
        retv_level, curr_level = 0, 0
        max_value = float("-inf")
        while queue:
            curr_level += 1
            length = len(queue)
            curr_sum = 0
            while length > 0:
                node = queue.popleft()
                curr_sum += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                length -= 1
            if curr_sum > max_value:
                max_value = curr_sum
                retv_level = curr_level
        return retv_level


所属网站分类: 技术文章 > 博客

作者:我是防疫小可爱

链接:https://www.pythonheidong.com/blog/article/256367/9e290defcef0319cba0f/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

28 0
收藏该文
已收藏

评论内容:(最多支持255个字符)