代码随想录：二叉树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;}
}