LeetCode赛题515----Find Largest Element in Each Row
2024-08-30 18:15:22
问题描述
You need to find the largest element in each row of a Binary Tree.
Example:
Input:
1
/ \
2 3
/ \ \
5 3 9
Output: [1, 3, 9]
算法分析
使用两个队列,逐层遍历二叉树的各个节点,每个队列中的节点都是同一层的节点,在遍历一层时,找出该层最大的节点值加入ArrayList中。
Java算法实现:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int[] findValueMostElement(TreeNode root) {
if(root==null){
int[] tmp=new int[0];
return tmp;
}
ArrayList<Integer>arr=new ArrayList<>();
Queue<TreeNode>que1=new LinkedList<>();
Queue<TreeNode>que2=new LinkedList<>();
que1.add(root);
int max;
while(!que1.isEmpty()||!que2.isEmpty()){
max=Integer.MIN_VALUE;
if(!que1.isEmpty()){
while(!que1.isEmpty()){
TreeNode node=que1.poll();
if(node.val>max){ //找到该层的最大值
max=node.val;
}
if(node.left!=null){
que2.add(node.left);
}
if(node.right!=null){
que2.add(node.right);
}
}
arr.add(max);
}
else if(!que2.isEmpty()){
while(!que2.isEmpty()){
TreeNode node=que2.poll();
if(node.val>max){
max=node.val;
}
if(node.left!=null){
que1.add(node.left);
}
if(node.right!=null){
que1.add(node.right);
}
}
arr.add(max);
}
}
int [] ans=new int[arr.size()];
for(int i=0;i<ans.length;i++){
ans[i]=arr.get(i);
}
return ans;
}
}
最新文章
- STEP模块——电子琴
- Java编译器如何生成重载和覆盖方法代码
- 安装DirectX SDK (June 2010) 失败(Error Code S1023)(转)
- C# SerialPort的简单使用
- 创建对象的两种方法: new 和 面向对象(对象字面量)及对象属性访问方法
- AutoCompleteTextview、MultiAutoCompleteTextView
- java上传并下载以及解压zip文件有时会报文件被损坏错误分析以及解决
- Java设计模式总汇一
- 【转】Nginx配置详解
- 记一次尴尬的git reset丢失分支故障
- table-一列细分为多列(合并单元格)
- Python语言——基础01-环境安装、注释、变量
- [原创]K8Cscan插件之Windows密码爆破
- Windows系统下PHP使用Redis
- [LeetCode] 704. Binary Search_Easy tag: Binary Search
- 2018-2019-1 20189206 vim.c插件安装
- div+css网页标准布局实例教程(一)
- hdu1301 Jungle Roads 最小生成树
- SharePoint研究之表单登录配置
- MySQL中视图和普通表的区别