本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).
Example 1:
Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]
Example 2:
Input: root = [1,2,3]
Output: [1,3]
Example 3:
Input: root = [1]
Output: [1]
Example 4:
Input: root = [1,null,2]
Output: [1,2]
Example 5:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree will be in the range
[0, 104].
-231 <= Node.val <= 231 - 1
在每个树行中找最大值。题意是给一个二叉树，请返回每一层里最大的node.val。
这道题其实很简单，BFS和DFS都能做，着重掌握DFS的方法。
BFS
就是普通的层序遍历，遍历的时候记录每一层上的最大值，放入结果集即可。
时间O(n)
空间O(n)
Java实现
1 class Solution {
2 public List<Integer> largestValues(TreeNode root) {
3 List<Integer> res = new ArrayList<>();
4 // corner case
5 if (root == null) {
6 return res;
7 }
8 // normal case
9 Queue<TreeNode> queue = new LinkedList<>();
10 queue.offer(root);
11 while (!queue.isEmpty()) {
12 int size = queue.size();
13 int max = Integer.MIN_VALUE;
14 for (int i = 0; i < size; i++) {
15 TreeNode cur = queue.poll();
16 max = Math.max(max, cur.val);
17 if (cur.left != null) {
18 queue.offer(cur.left);
19 }
20 if (cur.right != null) {
21 queue.offer(cur.right);
22 }
23 }
24 res.add(max);
25 }
26 return res;
27 }
28 }
DFS
DFS的做法是在比较当前结果集的size和树的深度level。如果当前res.size + 1 == level，说明DFS已经在处理下一层了，此时先把下一层的root节点放到结果集。在遍历当前层的时候，如果res.size == level，则需要把结果集中当前层的那个最大值拿出来跟当前遍历到的节点值作比较，并把较大的那一个再更新回结果集。这里有一个有配图的题解，帮助理解DFS是怎么运行的。
时间O(n)
空间O(n)
Java实现
1 class Solution {
2 public List<Integer> largestValues(TreeNode root) {
3 List<Integer> res = new ArrayList<>();
4 // corner case
5 if (root == null) {
6 return res;
7 }
8 helper(res, root, 1);
9 return res;
10 }
11
12 private void helper(List<Integer> res, TreeNode root, int depth) {
13 if (root == null) {
14 return;
15 }
16 if (depth == res.size() + 1) {
17 res.add(root.val);
18 } else {
19 res.set(level - 1, Math.max(res.get(level - 1), root.val));
20 }
21 helper(res, root.left, depth + 1);
22 helper(res, root.right, depth + 1);
23 }
24 }
LeetCode 题目总结
