跳到主要内容

剑指 Offer II 044.二叉树每层的最大值

· 阅读需 3 分钟

1、题干​

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

解法1：DFS递归实现​

DFS递归遍历树的每个节点，递归函数的形参中添加1个层级参数，便于计算每层节点最大值。

执行结果​

1.png

代码​

var largestValues = function (root) {
    const res = [];
    function dfs(node, level) {
        if (!node) return;
        if (res[level] === undefined || node.val > res[level]) res[level] = node.val;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return res;
};

解法2：BFS非递归实现​

BFS非递归遍历树的每个节点，需要借助队列实现。与常规BFS非递归实现不同，此处队列是一个矩阵，队列中的元素是每层节点的集合。

执行结果​

2.png

代码​

var largestValues = function (root) {
    const queue = root ? [[root]] : [], res = [];
    for (const curNodes of queue) {
        let max = -Infinity, nodes = [];
        for (const node of curNodes) {
            if (node.val > max) max = node.val;
            if (node.left) nodes.push(node.left);
            if (node.right) nodes.push(node.right);
        }
        if (nodes.length) queue.push(nodes);
        res.push(max);
    }
    return res;
};

由于非递归实现需要额外借助数组实现，且存在大量Array.push()等耗时操作，所以时间和空间上会消耗得更多