代码随想录：二叉树5
目录
102.二叉树的层序遍历
题目
代码（队列实现）
107.二叉树的层序遍历II
题目
代码
199.二叉树的右视图
题目
代码
637.二叉树的层平均值
题目
代码
102.二叉树的层序遍历
题目
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
代码（队列实现）
/*** 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<List<Integer>> levelOrder(TreeNode root) {//res保存每一层的结果集List<List<Integer>> res = new ArrayList<List<Integer>>();//如果根节点为空，直接返回if(root == null){return res;}//que队列，用来保存访问过但还没处理的节点Queue<TreeNode> que = new ArrayDeque<>();que.offer(root); //根节点入队，队列有一个节点//当队列非空，说明还有节点没处理while(!que.isEmpty()){int len = que.size(); //当前队列长度就是这一层的元素个数List<Integer> tmpRes = new ArrayList<>(); //用来保存这一层的结果值//逐个处理这一层的每个节点while(len > 0){TreeNode tmp = que.poll(); //出队tmpRes.add(tmp.val); //加入暂时结果集//左孩子进队if(tmp.left != null){que.offer(tmp.left);}//右孩子进队if(tmp.right != null){que.offer(tmp.right);}len--;} res.add(tmpRes); //加入单层结果集}return res;}
}107.二叉树的层序遍历II
题目
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
代码
/*** 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<List<Integer>> levelOrderBottom(TreeNode root) {//res保存每一层的结果集List<List<Integer>> res = new ArrayList<List<Integer>>();//如果根节点为空，直接返回if(root == null){return res;}//que队列，用来保存访问过但还没处理的节点Queue<TreeNode> que = new ArrayDeque<>();que.offer(root); //根节点入队，队列有一个节点//当队列非空，说明还有节点没处理while(!que.isEmpty()){int len = que.size(); //当前队列长度就是这一层的元素个数List<Integer> tmpRes = new ArrayList<>(); //用来保存这一层的结果值//逐个处理这一层的每个节点while(len > 0){TreeNode tmp = que.poll(); //出队tmpRes.add(tmp.val); //加入暂时结果集//左孩子进队if(tmp.left != null){que.offer(tmp.left);}//右孩子进队if(tmp.right != null){que.offer(tmp.right);}len--;} res.add(tmpRes); //加入单层结果集}//把自顶而下的层序遍历逆序List<List<Integer>> lastres = new ArrayList<List<Integer>>();for(int i = res.size()-1; i >= 0; i--){lastres.add(res.get(i));}return lastres;}
}199.二叉树的右视图
题目
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
代码
/*** 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> rightSideView(TreeNode root) {//res保存每一层的结果集List<List<Integer>> res = new ArrayList<List<Integer>>();//保存返回结果List<Integer> lastres = new ArrayList<>();//如果根节点为空，直接返回if(root == null){return lastres;}//que队列，用来保存访问过但还没处理的节点Queue<TreeNode> que = new ArrayDeque<>();que.offer(root); //根节点入队，队列有一个节点//当队列非空，说明还有节点没处理while(!que.isEmpty()){int len = que.size(); //当前队列长度就是这一层的元素个数List<Integer> tmpRes = new ArrayList<>(); //用来保存这一层的结果值//逐个处理这一层的每个节点while(len > 0){TreeNode tmp = que.poll(); //出队tmpRes.add(tmp.val); //加入暂时结果集//左孩子进队if(tmp.left != null){que.offer(tmp.left);}//右孩子进队if(tmp.right != null){que.offer(tmp.right);}len--;} res.add(tmpRes); //加入单层结果集}//返回每一次的最右（最后）元素for(int i=0; i < res.size(); i++){List<Integer> tmpRes = res.get(i);lastres.add(tmpRes.get(tmpRes.size()-1));}return lastres;}
}637.二叉树的层平均值
题目
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11]
代码
/*** 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<Double> averageOfLevels(TreeNode root) {//res保存层序遍历结果List<List<Integer>> res = new ArrayList<List<Integer>>();List<Double> lastres = new ArrayList<>();//如果根节点为空，直接返回if(root == null){return lastres;}//que队列，用来保存访问过但还没处理的节点Queue<TreeNode> que = new ArrayDeque<>();que.offer(root); //根节点入队，队列有一个节点//当队列非空，说明还有节点没处理while(!que.isEmpty()){int len = que.size(); //当前队列长度就是这一层的元素个数List<Integer> tmpRes = new ArrayList<>(); //用来保存这一层的结果值//逐个处理这一层的每个节点while(len > 0){TreeNode tmp = que.poll(); //出队tmpRes.add(tmp.val); //加入暂时结果集//左孩子进队if(tmp.left != null){que.offer(tmp.left);}//右孩子进队if(tmp.right != null){que.offer(tmp.right);}len--;} res.add(tmpRes); //加入单层结果集}//计算每一层的平均值for(int i = 0; i < res.size(); i++){List<Integer> tmplist = res.get(i);double sum = 0;for(int j=0; j < tmplist.size(); j++){sum += tmplist.get(j);}lastres.add(sum/tmplist.size());}return lastres;}
}