在每个树行中找最大值

标签: 树 深度优先搜索 广度优先搜索 二叉树

难度: Medium

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
          1
         / \
        3   2
       / \   \  
      5   3   9

示例2：

输入: root = [1,2,3]
输出: [1,3]
解释:
          1
         / \
        2   3

示例3：

输入: root = [1]
输出: [1]

示例4：

输入: root = [1,null,2]
输出: [1,2]
解释:      
           1 
            \
             2

示例5：

输入: root = []
输出: []

提示：

  • 二叉树的节点个数的范围是 [0,104]
  • -231 <= Node.val <= 231 - 1

注意：本题与主站 515 题相同： https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/

Submission

运行时间: 29 ms

内存: 18.1 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        ret,queue=[],deque()
        if root:
            queue.append(root)
        while queue:
            num=-float('inf')
            for i in range(len(queue)):
                q=queue.popleft()
                num=max(num,q.val)
                if q.left:
                    queue.append(q.left)
                if q.right:
                    queue.append(q.right)
            ret.append(num)
        return ret

Explain

这个题解使用了广度优先搜索（BFS）的方法来遍历二叉树。首先，创建一个队列来保存待处理的节点，以及一个列表来保存每一层的最大值。对于树中的每一层，我们从队列中移除当前层的所有节点，并在此过程中找到这一层的最大值。然后将该层的最大值添加到结果列表中。同时，如果当前节点有子节点，就将这些子节点添加到队列中，以便在下一轮中处理。重复这个过程直到队列为空，即所有层都被处理完毕。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        ret, queue = [], deque()  # 初始化结果列表和队列
        if root:
            queue.append(root)  # 如果根节点存在，加入队列
        while queue:  # 当队列非空时
            num = -float('inf')  # 用于记录当前层的最大值
            for i in range(len(queue)):  # 处理当前层的所有节点
                q = queue.popleft()  # 从队列中取出节点
                num = max(num, q.val)  # 更新当前层的最大值
                if q.left:  # 如果左子节点存在，加入队列
                    queue.append(q.left)
                if q.right:  # 如果右子节点存在，加入队列
                    queue.append(q.right)
            ret.append(num)  # 将当前层的最大值加入结果列表
        return ret

Explore

使用广度优先搜索（BFS）的优势在于它能自然按层次遍历树结构，这使得计算每层的最大值变得直接和高效。BFS能够确保每次处理完一个层级的所有节点后再移向下一个层级，这对于需要按层次顺序处理数据的问题（如本题）非常合适。相比之下，深度优先搜索（DFS）会深入到某一条路径的末端，然后再回溯，这使得它在需要处理层级数据时可能需要额外的数据结构来记录节点的层级信息。然而，BFS的缺点是在最坏情况下可能需要更多的内存来存储所有同层的节点，特别是在树的宽度很大时。DFS通常使用的栈空间小于BFS在队列中需要的空间，尤其是在树较深且每层节点不均匀时。

使用 `-float('inf')` 作为每层最大值的初始化是一种通用方法，它确保了任何可能的节点值都会被正确地比较，无论这些值是正数、负数还是零。即使在所有节点值都是正数的情况下，使用 `-float('inf')` 也不会有问题，因为它总是小于任何正数，因此可以正确地更新最大值。然而，如果知道节点值的可能范围，也可以选择一个更合适的初始最小值，比如如果节点值都在 0 到 1000 之间，可以使用 `-1` 作为初始值。但总体来说，`-float('inf')` 提供了一种无需额外信息即可安全使用的方法。

在 Python 中，整数类型（int）是动态的，可以自动扩展以容纳大整数，因此在 Python 中通常不需要担心整数溢出问题。这意味着无论节点的值有多大或多小，Python 都能够正确处理，不会像在一些其他语言（如 C 或 Java）中那样遇到整数溢出的问题。然而，在使用其他可能有整数限制的编程语言时，确实需要考虑这个问题，并可能需要采取额外的措施来防止溢出，例如使用更大的数据类型或在计算过程中进行检查。