刷题顺序及思路来源于代码随想录，网站地址：https://programmercarl.com
二叉树的定义及创建见：
LeetCode ACM模式——二叉树篇（一）_要向着光的博客-CSDN博客
目录
102. 二叉树的层序遍历
利用队列
利用递归
107. 二叉树的层序遍历 II
199. 二叉树的右视图
637. 二叉树的层平均值
429. N 叉树的层序遍历
515. 在每个树行中找最大值
102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
利用队列
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
* @author light
* @Description 二叉树的层序遍历
*
*
* (利用队列：先进先出
* @create 2023-08-15 14:17
*/
public class levelOrderTest {
public static void main(String[] args) {
Integer[] arr={3,9,20,null,null,15,7};
BinaryTree2 tree2=new BinaryTree2(arr); //按数组方式创建二叉树
List<List<Integer>> res=levelOrder(tree2.root);
System.out.println(res);
}
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result=new ArrayList<>();
Deque<TreeNode> que=new ArrayDeque<>(); //队列
if(root==null){
return result;
}
que.offer(root);
while(!que.isEmpty()){
List<Integer> list=new ArrayList<>();
int size=que.size();
while(size>0){
TreeNode node = que.poll();
list.add(node.val);
if(node.left!=null){
que.offer(node.left);
}
if(node.right!=null){
que.offer(node.right);
}
size--;
}
result.add(list);
}
return result;
}
}
利用递归
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
* @author light
* @Description 二叉树的层序遍历
*
* @create 2023-08-15 14:17
*/
public class levelOrderTest {
public static void main(String[] args) {
Integer[] arr={3,9,20,null,null,15,7};
BinaryTree2 tree2=new BinaryTree2(arr); //按数组方式创建二叉树
List<List<Integer>> res1=levelOrder2(tree2.root);
System.out.println(res1);
}
public static List<List<Integer>> l=new ArrayList<>();
public static List<List<Integer>> levelOrder2(TreeNode root) {
checkFun(root,0);
return l;
}
public static void checkFun(TreeNode root,int deep){
if(root==null){
return ;
}
deep++;
if(l.size()<deep){
List<Integer> item=new ArrayList<>();
l.add(item);
}
l.get(deep-1).add(root.val);
checkFun(root.left,deep);
checkFun(root.right,deep);
}
}
107. 二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
199. 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
* @author light
* @Description 二叉树的右视图
*
*
* 思路：
* 层序遍历的时候，判断是否遍历到单层的最后面的元素，
* 如果是，就放进result数组中，随后返回result就可以了。
* @create 2023-08-15 17:49
*/
public class RightSideViewTest {
public static void main(String[] args) {
Integer[] arr={1,2,3,null,5,null,4};
BinaryTree2 tree2=new BinaryTree2(arr); //按数组方式创建二叉树
List<Integer> res=rightSideView(tree2.root);
System.out.println(res);
}
public static List<Integer> rightSideView(TreeNode root) {
List<Integer> list=new ArrayList<>();
Deque<TreeNode> que=new ArrayDeque<>();
if(root==null){
return list;
}
que.offer(root);
while(!que.isEmpty()){
int size=que.size();
while(size>0){
TreeNode node = que.poll();
if(size==1){
list.add(node.val);
}
if(node.left!=null){
que.offer(node.left);
}
if(node.right!=null){
que.offer(node.right);
}
size--;
}
}
return list;
}
}
637. 二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
* @author light
* @Description 二叉树的层平均值
* @create 2023-08-15 18:23
*/
public class AverageOfLevelsTest {
public static void main(String[] args) {
Integer[] arr={3,9,20,null,null,15,7};
BinaryTree2 tree2=new BinaryTree2(arr); //按数组方式创建二叉树
List<Double> res=averageOfLevels(tree2.root);
System.out.println(res);
}
public static List<Double> averageOfLevels(TreeNode root) {
Deque<TreeNode> que=new ArrayDeque();
List<Double> list=new ArrayList();
if(root==null){
return list;
}
que.add(root);
while(!que.isEmpty()){
int size=que.size();
int count=size;
Double valSum=0.0;
while((size--!=0)){
TreeNode node=que.peek();
valSum+=node.val;
if(node.left!=null){
que.add(node.left);
}
if(node.right!=null){
que.add(node.right);
}
que.remove();
}
list.add(valSum/count);
}
return list;
}
}
429. N 叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
这道题按照题目创建n叉树这里我一直有问题，所以就只给出核心代码
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res=new ArrayList<>();
if(root==null){
return res;
}
Deque<Node> que=new ArrayDeque<>();
que.offer(root);
while(!que.isEmpty()){
List<Integer> list=new ArrayList<>();
int size=que.size();
while (size>0){
Node node=que.poll();
list.add(node.val);
List<Node> children=node.children;
if(children!=null){
for(Node n:children){
que.add(n);
}
}
size--;
}
res.add(list);
}
return res;
}
}515. 在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
* @author light
* @Description 在每个数行中找到最大值
*
*
* @create 2023-08-15 20:58
*/
public class LargestValuesTest {
public static void main(String[] args) {
Integer[] arr={1,3,2,5,3,null,9};
BinaryTree2 tree2=new BinaryTree2(arr); //按数组方式创建二叉树
List<Integer> res=largestValues(tree2.root);
System.out.println(res);
}
public static List<Integer> largestValues(TreeNode root) {
List<Integer> list=new ArrayList<>();
Deque<TreeNode> que=new ArrayDeque<>();
if(root==null){
return list;
}
que.offer(root);
while(!que.isEmpty()){
int size=que.size();
int max=que.peek().val;
while (size>0){
TreeNode node=que.poll();
if(node.left!=null){
que.offer(node.left);
}
if(node.right!=null){
que.offer(node.right);
}
max=max>node.val?max:node.val;
size--;
}
list.add(max);
}
return list;
}
}
