二叉树每层最大值 Posted on 2022-06-24 00:00:00 2022-06-24 00:00:00 by Author 摘要 给定一棵二叉树，找到二叉树每层最大的值 # 每行最大数 1. 题目描述 - 给定一棵二叉树的根节点 `root` ，请找出该二叉树中每一层的最大值。 - **提示：** - 二叉树的节点个数的范围是 `[0,104]` - -231 <= Node.val <= 231 - 1` 2. 示例描述 - 示例一 - 图片地址:leet_code_515_1.png ```java 输入：root = [1,3,2,5,3,null,9] 输出：[1,3,9] ``` - 示例二 - leet_code_515_2.png ```java 输入： root = [4,2,6,6,7,89,8,1,2,4,5] 输出：[4,6,89,5] ``` 3. 解题思路 - 今天无意之间进入leetcode，看见这道题做完之后，发现好久没更新自己的博客 ，自己博客好久没更新了，最近自己在搞实验，最近实验搞得差不多了。然后慢慢闲下来了。想着自己慢慢还是更新博客，距上次更新博客还是3个月以前，3个月以前的那一篇博客还是一篇水博客。 - 这道题是leetcode的第515题，链接为:[每行最大数](https://leetcode.cn/problems/find-largest-value-in-each-tree-row/)，首先看见题目就是一个二叉树的题目，对于二叉树的题，在我认知范围内，几乎和遍历有关或者和构建二叉树有关，这道题就是二叉树的层次遍历，只不过在层次遍历过程中加上了一个限制，即就是找出所给二叉树的每一层值最的节点。 - 对于层次遍历二叉树，所用的数据结构为队列。在[二叉树层次遍历](http://www.geticsen.cn/view/articles/detail/4948f372-28b9-406e-913a-dbc23effa70a)中我自己讲过，这道题只是在此基础上增加了一个判断。并且我在原有的基础上简化了代码。首先这道题难点在于在队列中怎么判断每一层的开始位置和结束位置。这里运用双指针思想。首先一个指针指向每一层的首节点，一个指针指向该层的尾节点，那么我们怎么知道哪个节点是该层的尾节点。这里我们拿示例一举例，首先对于第一层只有一个节点，我们设置首节点指向节点1前面，这里设置值为0，尾节点设置为1，表示指向该节点。此时队列进入根节点。然后从队列中出元素，每次从队列出元素时，首节点需要向后移动，当首节点与尾节点相遇的时候，那么该层遍历完成，所以当根节点出队时，首指针节点加一，此时首指针节点与尾指针节点相遇，说明该层遍历完成。需注意的时候，每次出队的元素节点，还有判断它是否有还在节点，如果有孩子节点，那么需要把孩子节点加入到队列中，那么当首指针与尾节点指针相遇，该层遍历完成，说明该层下一层的节点也成功进入队列中，这样也可以知道下一层队首开始节点与队尾节点了。如此反复。知道队列元素为空，那么这颗二叉树也遍历完成。 - 以上过程是找到每一层的首节点与未节点。那么怎么判断每一层最大的就节点尼。其实很简单，我们都知道每一层的首节点和每一层的尾节点，那么从首指针节点遍历到尾指针节点，找到最大值最大的节点即可。代码如下所示。 4. 代码示例 ```java public List<Integer> largestValues(TreeNode root) { //结果集合 List<Integer> result = new ArrayList<>(); //定义一个队列 Queue<TreeNode> queue = new ArrayDeque<>(); //如果根节点为空，不需要遍历，直接返回空 if (root == null) return result; //把根节点加入队列中 queue.add(root); //定义双指针，一个指向层首节点，一个指向该层的尾节点 //对于第一层首节点之前第一个节点之前，设置为0，尾节点指向根节点。 //mid是一个中间节点，记录上一层的尾节点位置。 int start = 0, mid = 1, end = 1; int max = Integer.MIN_VALUE; //由根节点遍历整个二叉树 while (!queue.isEmpty()) { //出队 TreeNode temp = queue.poll(); //首节点后移 start++; //在此过程中找到每层最大的节点 if (temp.val >= max) max = temp.val; //并且出队过程中，把下一层的节点加入队列中 //加入左节点 if (temp.left != null) { queue.add(temp.left); end++; } //加入右节点 if (temp.right != null) { queue.add(temp.right); end++; } //如果首指针与该层尾指针相遇， //并且在此过程中找到的最大值加入最终结果集合中 //更新下一层队尾节点为mid，记录下层队尾节点的位置 //而end节点继续寻找下下一层队尾的位置 if (start == mid) { result.add(max); max = Integer.MIN_VALUE; mid = end; } } //返回最终结果 return result; } ```
{{ item.content }}
{{ child.content }}