515. 在每个树行中找最大值

给定一棵二叉树的根节点 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}\le Node.val\le 2^{31}-1$

解法一(BFS+队列)

思路分析：

1. 使用二叉树的层序遍历，对每层进行遍历
2. 在对每层进行遍历时，寻找每层的最大值，并保存

实现代码如下：

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> ans = new ArrayList<>();if (root == null)return ans;		// 排除边界条件Queue<TreeNode> queue = new ArrayDeque<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();int max = Integer.MIN_VALUE;	// 标记该层最大值for (int i = 0; i < size; ++ i) {TreeNode node = queue.poll();max = Math.max(max, node.val);if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}ans.add(max);	// 记录保存每层最大值}return ans;}return ans;}
}

提交结果如下：

解答成功:
执行耗时:2 ms,击败了87.47% 的Java用户
内存消耗:44.1 MB,击败了9.26% 的Java用户

复杂度分析：

• 时间复杂度：$O(n)$，遍历二叉树
• 空间复杂度：$O(n)$，辅助队列

解法二(递归+dfs)

思路分析：

1. 可以使用递归深度优先搜索去寻找每层的最大值。
2. 首先思考递归的参数和返回值，因为需要寻找每层的最大值，所以需要一个变量来标记节点所在层数，同时需要传递二叉树的节点，以及需要保存结果的列表参数；同时不需要返回值
3. 思考递归的边界条件，对于递归寻找某层二叉树结点的最大值，当结点为空时，即不需要判断是否为最大值，直接返回即可，且此时也意味着遍历到二叉树末端
4. 思考递归的过程，对于某个二叉树结点，首先需要判断其所在层 在此之前是否有递归到过，如果有，则将其结点值与此时列表中的结点值进行比较，若没有递归过，则直接将其保存到结果列表中

实现代码如下：

class Solution {// 递归+dfspublic List<Integer> largestValues(TreeNode root) {List<Integer> ans = new ArrayList<>();dfs(root, 0, ans);return ans;}private void dfs(TreeNode node, int deeply, List<Integer> ans) {if (node == null)return ;	// 递归边界if (deeply >= ans.size()) {	// 该层未曾出现过ans.add(node.val);} else {	// 若该层出现过 比较得出更大值Integer num = ans.get(deeply);if (num < node.val) {ans.set(deeply, node.val);}}dfs(node.left, deeply+1, ans);dfs(node.right, deeply+1, ans);}
}

提交结果如下：

解答成功:
执行耗时:1 ms,击败了96.80% 的Java用户
内存消耗:44.4 MB,击败了5.04% 的Java用户

复杂度分析：

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