代码随想录刷题学习日记

仅为个人记录复盘学习历程，解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

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;}