币圈小鱼儿
【霍比特交易所怎么样】算法题 375：在每个树行中找最大值
摘要：在二叉树的每一行中找到最大的值。
来源： 数据结构和算法-山大王 wld
问题描述
在二叉树的每一行中找到最大的值。
比如
输入 :
1 / 3 2 / 5 3 9输出 : [1, 3, 9]
问题分析：
**
**
01 BFS 求解
关于这道题我们最容易想到的也就是 BFS，一层一层遍历，然后在每一层中再找出最大值。前面已经讲过很多 BFS 的题，这题不是很难。我们来直接看下代码。
1public List largestValues(TreeNode root) { 2 //LinkedList 实现队列 3 Queue queue = new LinkedList<>(); 4 List values = new ArrayList<>(); 5 if (root != null) 6 queue.add(root);// 入队 7 while (!queue.isEmpty()) { 8 int max = Integer.MIN_VALUE; 9 int levelSize = queue.size();// 每一层的数量 10 for (int i = 0; i < levelSize; i++) { 11 TreeNode node = queue.poll();// 出队 12 max = Math.max(max, node.val);// 记录每层的最大值 13 if (node.left != null) 14 queue.add(node.left); 15 if (node.right != null) 16 queue.add(node.right); 17 } 18 values.add(max); 19 } 20 return values; 21}
02DFS 求解
除了一层一层遍历以外，我们还可以使用 DFS （深度优先搜索算法）来求解。我们就以上面的举例来画个图分析一下
上面的橙色结点就是遍历的顺序，看明白了上面的图，代码就很容易写出来了，我们再来看下代码
1public List largestValues(TreeNode root) { 2 List res = new ArrayList<>(); 3 helper(root, res, 1); 4 return res; 5} 6 7//level 表示的是第几层，集合 res 中的第一个数据表示的是 8// 第一层的最大值，第二个数据表示的是第二层的最大值…… 9private void helper(TreeNode root, List res, int level) { 10 if (root == null) 11 return; 12 // 如果走到下一层了直接加入到集合中 13 if (level == res.size() + 1) { 14 res.add(root.val); 15 } else { 16 // 注意：我们的 level 是从 1 开始的，也就是说 root 17 // 是第一层，而集合 list 的下标是从 0 开始的， 18 // 所以这里 level 要减 1。 19 // Math.max(res.get(level - 1), root.val) 表示的 20 // 是遍历到的第 level 层的 root.val 值和集合中的第 level 21 // 个元素的值哪个大，就要哪个。 22 res.set(level - 1, Math.max(res.get(level - 1), root.val)); 23 } 24 // 下面两行是 DFS 的核心代码 25 helper(root.left, res, level + 1); 26 helper(root.right, res, level + 1); 27}
- 免责声明
- 世链财经作为开放的信息发布平台，所有资讯仅代表作者个人观点，与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论，请提供相关材料，发送到：2785592653@qq.com。
- 风险提示：本站所提供的资讯不代表任何投资暗示。投资有风险，入市须谨慎。
- 世链粉丝群：提供最新热点新闻，空投糖果、红包等福利，微信：juu3644。
