👊3.二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
题目链接：二叉树的右视图https://leetcode-cn.com/problems/binary-tree-right-side-view/
这道题目的要求要的是每一层结点的最后一个节点，我们同样利用相同的代码模板进行改动，但希望大家不要复制，每次都尝试自己去手写，然后想想该改动什么地方。这里我们在list加入时，只加入path的最后一个元素即可的得到答案。
注意返回值不同了。
class Solution { List<Integer> list=new ArrayList<>(); public List<Integer> rightSideView(TreeNode root) { dfs(root); return list; } public void dfs(TreeNode root){ if(root==null) return; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ List<Integer> itemlist=new ArrayList<>(); int len=queue.size(); while(len>0){ TreeNode x=queue.poll(); itemlist.add(x.val); if(x.left!=null) queue.offer(x.left); if(x.right!=null) queue.offer(x.right); len--; } //主要改动的地方 list.add(itemlist.get(itemlist.size()-1)); } } }
👊4.二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
二叉树的层平均值https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
这道题最容易出错的地方是：结点的值可以取到int的极大和极小，所以会爆int。由于我们不需要去统计每层的元素，只需要统计每层元素之和，但是要用long去存储，否则就会爆int。然后每次遍历一层后计算出平均值放入答案数组中。
class Solution { //注意这里要用Double List<Double> list=new ArrayList<>(); public List<Double> averageOfLevels(TreeNode root) { dfs(root); return list; } public void dfs(TreeNode root){ if(root==null) return; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ //没注意这里错了，有可能爆int long sum=0; int len=queue.size(); int count=len; while(len>0){ TreeNode x=queue.poll(); sum+=x.val; if(x.left!=null) queue.offer(x.left); if(x.right!=null) queue.offer(x.right); len--; } list.add((double)sum/count); } } }
👊5.N叉数的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
题目链接：N叉数的层序遍历https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
这题目同样是套用我们的模板，与第一题唯一的区别就是多了几个子结点而已，我们在递归时对每个子节点都递归一下就行了，只需要改动一下即可。
class Solution { List<List<Integer>> list=new ArrayList<>(); public List<List<Integer>> levelOrder(Node root) { dfs(root); return list; } public void dfs(Node root){ if(root==null) return; Queue<Node> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ List<Integer> itemlist=new ArrayList<>(); int len=queue.size(); while(len>0){ Node x=queue.poll(); itemlist.add(x.val); //只需要改动这里即可 for(int i=0;i<x.children.size();i++){ if(x.children.get(i)!=null){ queue.offer(x.children.get(i)); } } len--; } list.add(new ArrayList(itemlist)); } } }
👊6.在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
题目链接：在每个树行中找最大值https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
这道题要求找出每一层的最大值，我们需要在每层遍历的时候去记录下它的最大值，然后放入答案数组即可，也是在原模板代码上改动即可。
class Solution { List<Integer> list=new ArrayList<>(); public List<Integer> largestValues(TreeNode root) { bfs(root); return list; } public void bfs(TreeNode root){ if(root==null) return; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int max=Integer.MIN_VALUE; int len=queue.size(); while(len-->0){ TreeNode x=queue.poll(); max=Math.max(max,x.val); if(x.left!=null) queue.offer(x.left); if(x.right!=null) queue.offer(x.right); } list.add(max); } } }
