LeetCode_二叉树_中等_515.在每个树行中找最大值

深藏阁楼爱情的钟 2023-10-06 23:36 38阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

**示例1：**  
![在这里插入图片描述][7500c4c6ad5c43398847c53abdd77fb1.png]  
输入: root = \[1,3,2,5,3,null,9\]  
输出: \[1,3,9\]

**示例2：**  
输入: root = \[1,2,3\]  
输出: \[1,3\]

**提示：**  
二叉树的节点个数的范围是 \[0,104\]  
\-231 <= Node.val <= 231 \- 1

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row

## 2.思路 ##

（1）层序遍历  
既然要找出该二叉树中每一层的最大值，那么可以通过层序遍历的方式来进行寻找，在遍历每一层时，使用遍历 curMax 来保存当前层的最大值，在每一层遍历结束后，将 curMax 加入到 res 中即可，遍历结束后返回 res。具体的遍历细节可参考[102.二叉树的层序遍历][102.]这篇文章。

（2）深度优先遍历 (DFS)  
具体细节可看下面代码中的注释。

## 3.代码实现（Java） ##

//思路1————层序遍历
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> largestValues(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            if (root == null) {
        
                return res;
            }
            //queue保存层序遍历过程中每一层的所有节点
            Queue<TreeNode> queue = new LinkedList<>();
            //最开始的第一层只有根节点，故先将根节点加入到队列中
            queue.offer(root);
            // while 循环控制从上向下方向的遍历
            while (!queue.isEmpty()) {
        
                int levelSize = queue.size();
                int curMax = Integer.MIN_VALUE;
                // for 循环控制每一层从左向右的遍历
                for (int i = 0; i < levelSize; i++) {
        
                    TreeNode curNode = queue.poll();
                    curMax = Math.max(curMax, curNode.val);
                    //将下一层中的所有节点保存到 queue 中
                    if (curNode.left != null) {
        
                        queue.offer(curNode.left);
                    }
                    if (curNode.right != null) {
        
                        queue.offer(curNode.right);
                    }
                }
                res.add(curMax);
            }
            return res;
        }
    }

//思路2————深度优先遍历 (DFS)
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        // res 保存最终结果
        List<Integer> res = new ArrayList<>();
        
        public List<Integer> largestValues(TreeNode root) {
        
            if (root == null) {
        
                return res;
            }
            dfs(root, 0);
            return res;
        }
        
        private void dfs(TreeNode root, int curHeight) {
        
        	/*
    			res 中的下标表示二叉树中的层数（从 0 开始），下标对应的值表示该层中的最大值
    		*/	
            if (curHeight == res.size()) {
        
            	/*
            		如果 curHeight == res.size()，那么则说明 res 还未保存当前第 curHeight 层
            		的最大值信息，所以直接将当前节点值加入到 res 中
    			*/
                res.add(root.val);
            } else {
        
            	// 更新当前层的最大值
                res.set(curHeight, Math.max(res.get(curHeight), root.val));
            }
            // 搜索左子树
            if (root.left != null) {
        
                dfs(root.left, curHeight + 1);
            }
            // 搜索右子树
            if (root.right != null) {
        
                dfs(root.right, curHeight + 1);
            }
        }
    }

[7500c4c6ad5c43398847c53abdd77fb1.png]: https://img-blog.csdnimg.cn/7500c4c6ad5c43398847c53abdd77fb1.png
[102.]: https://blog.csdn.net/weixin_43004044/article/details/123697874