当前位置：首页 > article >正文

剑指Offer|LCR 044.在每个树行中找最大值

article 2025/1/27 4:03:28

LCR 044.在每个树行中找最大值

给定一棵二叉树的根节点 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

法1：队列

分析：

初始化变量：当前层数的节点数current，下一层的节点数量next均为0，定义空的queue。

root不为空，直接加入队列。current设置为1个结点。

遍历queue，将root出队列，求出当前层次最大值，如果有左右孩子的话，就将左右孩子入队列，孩子是下一层节点，所以next需要++。当current为0的话，说明这一层的结点数遍历完了，所以将max也就是这一层的最大值存入result中，更新一下max、current和next。

var largestValues = function(root) {
    let current = 0; // 当前层数的节点数
    let next = 0; // 下一层的节点数量
    let queue = []; // 用来存放待遍历的节点
    
    if (root !== null) {
        queue.push(root);
        current = 1;
    }

    let result = [];
    let max = -Infinity;
    
	 // 广度优先遍历整个树
    while (queue.length > 0) {
        let node = queue.shift();
        current--;
        max = Math.max(max, node.val);

        if (node.left !== null) {
            queue.push(node.left);
            next++;
        }

        if (node.right !== null) {
            queue.push(node.right);
            next++;
        }

        if (current === 0) {
            result.push(max);
            max = -Infinity;
            current = next;
            next = 0;
        }
    }

    return result;
};