515. 在每个树行中找最大值
题目描述
输入二叉树的根节点 root，树用层序数组表示，空位写 null。
根所在的层记为第 0 层，往下依次是第 1 层、第 2 层……对每一层求出该层所有节点值中的最大值。
按从上到下的层序返回这些最大值组成的数组。空树返回空数组。
示例 1
输入：root = [1,3,2,5,3,null,9] 输出：[1,3,9]
解释：三层的最大值分别是 1、max(3,2) = 3、max(5,3,9) = 9。
示例 2
输入：root = [1,2,3] 输出：[1,3]
解释：第 0 层为 1，第 1 层 2 和 3 中取 3。
数据范围
- 节点个数在
[0, 10^4]范围内。 -2^31 <= Node.val <= 2^31 - 1
解题思路：广度优先搜索（层序遍历）
按层处理就是层序遍历（BFS）。每轮开始时队列里恰好是一整层的节点，先记下 len(q)，只弹出这么多个节点，一边弹一边更新本层最大值，并把孩子放到队尾。本层弹完，最大值就确定了，追加到答案。
为什么正确
每轮 while 开始时，队列里恰好是同一层的全部节点，且按从左到右排列。
复杂度分析
时间 O(n)，每个节点进出队列各一次；空间 O(w)，w 为最宽一层的节点数。
易错点
best 不能初始化为 0（节点值可能全为负数），要用本层第一个节点的值或负无穷；另外必须先固定 len(q) 再循环，否则会把下一层的节点混进本层。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
ans = []
q = collections.deque([root] if root else [])
while q:
best = q[0].val
for _ in range(len(q)):
node = q.popleft()
best = max(best, node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(best)
return ansclass Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> q = new ArrayDeque<>();
if (root != null) q.add(root);
while (!q.isEmpty()) {
int best = q.peek().val;
for (int i = q.size(); i > 0; i--) {
TreeNode node = q.poll();
best = Math.max(best, node.val);
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
}
ans.add(best);
}
return ans;
}
}class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ans;
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
int best = q.front()->val;
for (int i = q.size(); i > 0; i--) {
TreeNode* node = q.front(); q.pop();
best = max(best, node->val);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
ans.push_back(best);
}
return ans;
}
};func largestValues(root *TreeNode) []int {
ans := []int{}
q := []*TreeNode{}
if root != nil {
q = append(q, root)
}
for len(q) > 0 {
best := q[0].Val
for i := len(q); i > 0; i-- {
node := q[0]
q = q[1:]
if node.Val > best {
best = node.Val
}
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, best)
}
return ans
}var largestValues = function(root) {
const ans = [];
let q = root ? [root] : [];
while (q.length) {
let best = q[0].val;
const next = [];
for (const node of q) {
best = Math.max(best, node.val);
if (node.left)
next.push(node.left);
if (node.right)
next.push(node.right);
}
ans.push(best);
q = next;
}
return ans;
};function largestValues(root: TreeNode | null): number[] {
const ans: number[] = [];
let q: TreeNode[] = root ? [root] : [];
while (q.length) {
let best = q[0].val;
const next: TreeNode[] = [];
for (const node of q) {
best = Math.max(best, node.val);
if (node.left)
next.push(node.left);
if (node.right)
next.push(node.right);
}
ans.push(best);
q = next;
}
return ans;
}其他解法
层序遍历天然按层处理，每层取最大值；深度优先搜索通过记录深度把节点归到对应层，两者都是线性时间。
解法 2：深度优先搜索 时间 O(n)，空间 O(h)
递归遍历时带上当前深度 depth。第一次到达某一层时，结果数组长度正好等于 depth，就把该节点值追加进去；之后再到达这一层的节点，就与已有值比较取最大。
不需要队列，额外空间只与树高有关，代码简短。但“每层”的概念不如层序遍历直观，树退化成链时递归会很深。
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
ans = []
def dfs(node, depth):
if not node:
return
# 第一次到达这一层时追加，之后取最大值
if depth == len(ans):
ans.append(node.val)
else:
ans[depth] = max(ans[depth], node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root, 0)
return ansclass Solution {
private List<Integer> ans = new ArrayList<>();
private void dfs(TreeNode node, int depth) {
if (node == null) return;
if (depth == ans.size()) ans.add(node.val);
else ans.set(depth, Math.max(ans.get(depth), node.val));
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
}
public List<Integer> largestValues(TreeNode root) {
dfs(root, 0);
return ans;
}
}class Solution {
public:
vector<int> ans;
void dfs(TreeNode* node, int depth) {
if (!node) return;
if (depth == (int)ans.size()) ans.push_back(node->val);
else ans[depth] = max(ans[depth], node->val);
dfs(node->left, depth + 1);
dfs(node->right, depth + 1);
}
vector<int> largestValues(TreeNode* root) {
dfs(root, 0);
return ans;
}
};func largestValues(root *TreeNode) []int {
ans := []int{}
var dfs func(node *TreeNode, depth int)
dfs = func(node *TreeNode, depth int) {
if node == nil {
return
}
if depth == len(ans) {
ans = append(ans, node.Val)
} else if node.Val > ans[depth] {
ans[depth] = node.Val
}
dfs(node.Left, depth+1)
dfs(node.Right, depth+1)
}
dfs(root, 0)
return ans
}var largestValues = function(root) {
const ans = [];
const dfs = (node, depth) => {
if (!node) return;
if (depth === ans.length) ans.push(node.val);
else ans[depth] = Math.max(ans[depth], node.val);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
};
dfs(root, 0);
return ans;
};function largestValues(root: TreeNode | null): number[] {
const ans: number[] = [];
const dfs = (node: TreeNode | null, depth: number): void => {
if (!node) return;
if (depth === ans.length) ans.push(node.val);
else ans[depth] = Math.max(ans[depth], node.val);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
};
dfs(root, 0);
return ans;
}