代码随想录刷题学习日记
仅为个人记录复盘学习历程,解题思路来自代码随想录
代码随想录刷题笔记总结网址:
代码随想录
107.二叉树的层序遍历 II
给定一个二叉树,返回其节点值自底向上的层次遍历。
提供参数:根结点root
主要思路:与二叉树的层序遍历大体相同,返回结果时将结果数组中的数据反转即可。
二叉树的层序遍历在上一次学习中学习过了不再赘述。
代码大致如下:
public List<List<Integer>> levelOrderBottom(TreeNode root) {//全局初始化,定义结果数组,定义队列List<List<Integer>>tempList=new ArrayList<>();Queue<TreeNode>queue=new LinkedList<TreeNode>();//若根为0,返回空数组if(root==null)return tempList;queue.offer(root);while(!queue.isEmpty()){//初始化每层的数据,每层的长度,用于接收每层的临时一维数组int len=queue.size();List<Integer>temp=new ArrayList<>();//对每层节点的操作for(int i=0;i<len;i++){TreeNode node=queue.poll();temp.add(node.val);if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}tempList.add(temp);}//反转临时存储数组,构造返回数组List<List<Integer>>res=new ArrayList<>();for(int i=tempList.size()-1;i>=0;i--){res.add(tempList.get(i));}return res;}
199.二叉树的右视图
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
提供参数:根结点root
主要思路:与二叉树的层序遍历大体相同,只需要在每层的遍历中加以判断是否是该层的最后一个,如果是则将该元素加入结果数组,返回结果时将结果数组返回即可。
二叉树的层序遍历在上一次学习中学习过了不再赘述。
代码大致如下:
public List<Integer> rightSideView(TreeNode root) {//初始化List<Integer>res=new ArrayList<>();Queue<TreeNode>queue=new LinkedList<TreeNode>();if(root==null)return res;queue.offer(root);while(!queue.isEmpty()){//初始化int len=queue.size();int right=0;for(int i=0;i<len;i++){TreeNode node=queue.poll();if(i==len-1) right=node.val;if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}res.add(right);}return res;}
637.二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
提供参数:根结点root
主要思路:与二叉树的层序遍历大体相同,只需要在每层的遍历中将每层的元素累加求和,并计算平均值加入结果数组,返回结果时将结果数组返回即可。
二叉树的层序遍历在上一次学习中学习过了不再赘述。
代码示例如下:
//List<Double>res=new ArrayList<>();Queue<TreeNode>queue=new LinkedList<TreeNode>();if(root==null)return res;queue.offer(root);while(!queue.isEmpty()){//double temp=0.0;int len=queue.size();for(int i=0;i<len;i++){TreeNode node=queue.poll();temp+=node.val;if(node.left!=null) queue.offer(node.left);if(node.right!=null) queue.offer(node.right);}temp/=len;res.add(temp);}return res;}
429.N叉树的层序遍历
给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。
提供参数:根节点root
主要思路:与二叉树的层序遍历大体相同,不同之处在于每个节点最多并不只有两个节点。
二叉树的层序遍历在上一次学习中学习过了不再赘述。
代码示例如下:
public List<List<Integer>> levelOrder(Node root) {//List<List<Integer>>res=new ArrayList<>();Queue<Node>queue=new LinkedList<Node>();if(root==null)return res;queue.offer(root);while(!queue.isEmpty()){int len=queue.size();List<Integer>temp=new ArrayList<>();for(int i=0;i<len;i++){Node node=queue.poll();temp.add(node.val);if(node.children!=null&&node.children.size()>0){for(Node n:node.children){queue.offer(n);}}}res.add(temp);}return res;}
515.在每个树行中找最大值
给定一棵二叉树的根节点 root
,请找出该二叉树中每一层的最大值。
提供参数:根结点root
主要思路:与二叉树的层序遍历大体相同,层序遍历时将每层最大值记录,加入到结果数组中,当队列为空时返回结果数组即可。
二叉树的层序遍历在上一次学习中学习过了不再赘述。
代码示例如下:
public List<Integer> largestValues(TreeNode root) {//List<Integer>res=new ArrayList<>();Queue<TreeNode>queue=new LinkedList<TreeNode>();if(root==null)return res;queue.offer(root);while(!queue.isEmpty()){int len=queue.size();//需注意这里Max初始化的数值int Max=Integer.MIN_VALUE;for(int i=0;i<len;i++){TreeNode node=queue.poll();Max=node.val>Max?node.val:Max;if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}res.add(Max);}return res;}