适合新手做的网站,集团网站建设管理制度,蛋糕店网页设计免费模板,小破站下载目录
102.二叉树的层序遍历
题目
代码#xff08;队列实现#xff09;
107.二叉树的层序遍历II
题目
代码
199.二叉树的右视图
题目
代码
637.二叉树的层平均值
题目
代码 102.二叉树的层序遍历
题目 给你二叉树的根节点 root #xff0c;返回其节点值的 层序遍…目录
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 ListListInteger levelOrder(TreeNode root) {//res保存每一层的结果集ListListInteger res new ArrayListListInteger();//如果根节点为空直接返回if(root null){return res;}//que队列用来保存访问过但还没处理的节点QueueTreeNode que new ArrayDeque();que.offer(root); //根节点入队队列有一个节点//当队列非空说明还有节点没处理while(!que.isEmpty()){int len que.size(); //当前队列长度就是这一层的元素个数ListInteger 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 ListListInteger levelOrderBottom(TreeNode root) {//res保存每一层的结果集ListListInteger res new ArrayListListInteger();//如果根节点为空直接返回if(root null){return res;}//que队列用来保存访问过但还没处理的节点QueueTreeNode que new ArrayDeque();que.offer(root); //根节点入队队列有一个节点//当队列非空说明还有节点没处理while(!que.isEmpty()){int len que.size(); //当前队列长度就是这一层的元素个数ListInteger 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); //加入单层结果集}//把自顶而下的层序遍历逆序ListListInteger lastres new ArrayListListInteger();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 ListInteger rightSideView(TreeNode root) {//res保存每一层的结果集ListListInteger res new ArrayListListInteger();//保存返回结果ListInteger lastres new ArrayList();//如果根节点为空直接返回if(root null){return lastres;}//que队列用来保存访问过但还没处理的节点QueueTreeNode que new ArrayDeque();que.offer(root); //根节点入队队列有一个节点//当队列非空说明还有节点没处理while(!que.isEmpty()){int len que.size(); //当前队列长度就是这一层的元素个数ListInteger 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 i0; i res.size(); i){ListInteger 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 ListDouble averageOfLevels(TreeNode root) {//res保存层序遍历结果ListListInteger res new ArrayListListInteger();ListDouble lastres new ArrayList();//如果根节点为空直接返回if(root null){return lastres;}//que队列用来保存访问过但还没处理的节点QueueTreeNode que new ArrayDeque();que.offer(root); //根节点入队队列有一个节点//当队列非空说明还有节点没处理while(!que.isEmpty()){int len que.size(); //当前队列长度就是这一层的元素个数ListInteger 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){ListInteger tmplist res.get(i);double sum 0;for(int j0; j tmplist.size(); j){sum tmplist.get(j);}lastres.add(sum/tmplist.size());}return lastres;}
}
