0515. 在每个树行中找最大值【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS

1. 📝 题目描述

• leetcode

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

示例 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

2. 🎯 s.1 - BFS

c

int* largestValues(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if (!root) return NULL;
    int* res = (int*)malloc(sizeof(int) * 10000);
    struct TreeNode* queue[10000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        int size = rear - front;
        int max = queue[front]->val;
        for (int i = 0; i < size; i++) {
            struct TreeNode* node = queue[front++];
            if (node->val > max) max = node->val;
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
        res[(*returnSize)++] = max;
    }
    return res;
}

js

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var largestValues = function (root) {
  if (!root) return []
  const res = []
  const queue = [root]
  while (queue.length) {
    let max = -Infinity
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const node = queue.shift()
      max = Math.max(max, node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    res.push(max)
  }
  return res
}

py

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

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

算法思路：

• 层序遍历，每层取最大值加入结果