Medium

题目描述

给定一个二叉树的根节点 root，返回树的每一行中的最大值（从第 0 行开始索引）。

示例 1：

输入：root = [1,3,2,5,3,null,9]
输出：[1,3,9]

示例 2：

输入：root = [1,2,3]
输出：[1,3]

提示：

  • 树中节点数目在范围 [0, 10^4] 内
  • -2^31 <= Node.val <= 2^31 - 1

解题思路

这是一道经典的二叉树层序遍历问题。我们需要找到每一层的最大值，有两种主要解法：

解法一：广度优先搜索（BFS）- 推荐 使用队列进行层序遍历，对于每一层，我们记录当前层的节点数量，然后遍历这一层的所有节点，找出最大值。这种方法直观且易于理解。

解法二：深度优先搜索（DFS） 使用递归的方式遍历树，同时记录当前节点所在的深度。维护一个结果数组，当访问到某一层的节点时，更新该层的最大值。

两种方法的时间复杂度都是 O(n)，其中 n 是树中节点的数量。空间复杂度方面，BFS 需要 O(w) 的队列空间（w 是树的最大宽度），DFS 需要 O(h) 的递归栈空间（h 是树的高度）。

对于这道题，BFS 更加直观，因为它天然地按层处理节点，符合题目要求。

代码实现

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (!root) return {};
        
        vector<int> result;
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            int maxVal = INT_MIN;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                maxVal = max(maxVal, node->val);
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            result.push_back(maxVal);
        }
        
        return result;
    }
};

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        queue = [root]
        
        while queue:
            level_size = len(queue)
            max_val = float('-inf')
            next_queue = []
            
            for _ in range(level_size):
                node = queue.pop(0)
                max_val = max(max_val, node.val)
                
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            
            result.append(max_val)
            queue = next_queue
        
        return result

public class Solution {
    public IList<int> LargestValues(TreeNode root) {
        if (root == null) return new List<int>();
        
        var result = new List<int>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            int maxVal = int.MinValue;
            
            for (int i = 0; i < levelSize; i++) {
                var node = queue.Dequeue();
                maxVal = Math.Max(maxVal, node.val);
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            result.Add(maxVal);
        }
        
        return result;
    }
}

var largestValues = function(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        let maxVal = -Infinity;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            maxVal = Math.max(maxVal, node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(maxVal);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
BFS解法O(n)O(w)
DFS解法O(n)O(h)

其中：

  • n 为二叉树中节点的总数
  • w 为二叉树的最大宽度
  • h 为二叉树的高度