刷算法Leetcode---8（二叉树篇）（层序遍历）
前言
本文是跟着代码随想录的栈与队列顺序进行刷题并编写的 代码随想录
二叉树的题目较多，就多分了几次写，这是第二篇
第一篇二叉树的文章链接：刷算法Leetcode---7（二叉树篇）（前中后序遍历）
这是力扣刷算法的其他文章链接：刷算法Leetcode文章汇总
二叉树篇（层序遍历）
（1）102. 二叉树的层序遍历
①bfs+队列，每层队列大小代表该层总节点数，每次取出一层的节点取值并加入左右孩子
②dfs，根节点从第0层开始，递归每个节点的左右孩子和层数，将层数作为下标加入结果。层数大于res的大小时，代表该层是第一次遍历到，要new ArrayList<>()加入res中
class Solution {
private List<List<Integer>> res;
public List<List<Integer>> levelOrder(TreeNode root) {
res = new ArrayList<>();
dfs(root,0);
return res;
}
private void dfs(TreeNode node,int depth){
if(node==null)return;
if(depth>=res.size())res.add(new ArrayList<>());
res.get(depth).add(node.val);
dfs(node.left,depth+1);
dfs(node.right,depth+1);
}
}（2）107. 二叉树的层序遍历 II
①bfs+队列，同102题，可直接将结果翻转，或者将每层结果level逆序加入res即可，res.add(0,level)
②dfs，同102题，可直接将结果翻转，或者遇到新层时头插res，层数作为逆序下标
（3）199. 二叉树的右视图
①bfs+队列，同102题，在获取每层节点时，只记录最后一个节点
②dfs，同102题，每次递归左右节点和层数，层数作为下标，若遇到同层节点就替换，否则直接添加
③dfs，大致同102题，但是先递归右节点再递归左节点，若遇到同层则忽略，否则直接添加
class Solution {
private List<Integer> res;
public List<Integer> rightSideView(TreeNode root) {
res = new ArrayList<>();
dfs(root,0);
return res;
}
private void dfs(TreeNode node,int depth){
if(node==null)return;
if(res.size()<=depth)res.add(node.val);
dfs(node.right,depth+1);
dfs(node.left,depth+1);
}
}（4）637. 二叉树的层平均值
①bfs+队列，同102题，记录每层节点数和总和，将平均值加入结果
②dfs，同102题，使用sum和count两个ArrayList记录每层的总和与个数，注意sum进行add时要用1.0乘
class Solution {
private List<Double> res;
private List<Double> sum;
private List<Integer> count;
public List<Double> averageOfLevels(TreeNode root) {
res = new ArrayList<>();
sum = new ArrayList<>();
count = new ArrayList<>();
dfs(root,0);
for(int i=0;i<sum.size();i++){
res.add(sum.get(i)/count.get(i));
}
return res;
}
private void dfs(TreeNode node,int depth){
if(node==null)return;
if(depth<sum.size()){
sum.set(depth,sum.get(depth)+node.val);
count.set(depth,count.get(depth)+1);
}
else{
sum.add(1.0*node.val);
count.add(1);
}
dfs(node.left,depth+1);
dfs(node.right,depth+1);
}
}（5）429. N 叉树的层序遍历
bfs+队列，同102题，但不是添加左右孩子，而是遍历添加所有的孩子节点，可用增强for循环
class Solution {
private List<List<Integer>> res;
private List<Integer> level;
private Deque<Node> queue;
public List<List<Integer>> levelOrder(Node root) {
res = new ArrayList<>();
queue = new ArrayDeque<>();
if(root==null)return res;
queue.addLast(root);
while(!queue.isEmpty()){
int num = queue.size();
level = new ArrayList<>();
for(int i=0;i<num;i++){
Node temp = queue.pollFirst();
level.add(temp.val);
for(Node child:temp.children){
queue.addLast(child);
}
}
res.add(level);
}
return res;
}
}（6）515. 在每个树行中找最大值
①bfs+队列，同102题，遍历每层节点时记录最大值
②dfs，同102题，遇到同层取更大值
（7）116. 填充每个节点的下一个右侧节点指针
①bfs+队列，同102题，遍历每层除最后一个节点外，next指针指向队头节点，即同层下一个节点
②dfs，同102题，遇到同层先将next指针指向新节点，再记录新节点
③bfs+next指针迭代，使用两个指针node1和node2实现，node1记录下一层最左节点用于标记下一层，node2遍历当前层，实现每个节点左右子节点的next连接，以及node2右节点和node2的next节点的左节点next连接。利用已有节点的next指针实现对一个层的遍历
class Solution {
public Node connect(Node root) {
if(root==null)return root;
Node node1=root,node2=null;
while(node1!=null&&node1.left!=null){
node2=node1;
node1=node1.left;
while(node2!=null){
node2.left.next=node2.right;
if(node2.next!=null)node2.right.next=node2.next.left;
node2=node2.next;
}
}
return root;
}
}④bfs+next指针递归，同上一种方法，使用递归实现
class Solution {
public Node connect(Node root) {
if(root==null)return root;
bfs(root);
return root;
}
private void bfs(Node node){
if(node==null||node.left==null)return;
Node temp = node;
while(temp!=null){
temp.left.next=temp.right;
if(temp.next!=null)temp.right.next=temp.next.left;
temp=temp.next;
}
bfs(node.left);
}
}⑤dfs，对每个节点，只用连接左右子节点和next的子节点即可，再递归左右子节点完成整颗树的连接
class Solution {
public Node connect(Node root) {
if(root==null||root.left==null)return root;
root.left.next=root.right;
root.right.next=root.next!=null?root.next.left:null;
connect(root.left);
connect(root.right);
return root;
}
}（8）117. 填充每个节点的下一个右侧节点指针 II
①bfs+队列，同116题方法一
②dfs，同116题方法二
③bfs+next指针迭代，使用nextLeftNode、currNode、preNode三个指针，nextLeftNode为下一层虚拟头节点标识下一层，currNode遍历当前层，preNode为下一层已遍历的最右边节点（便于下一层next指针连接）。遍历一层时，对于每个节点的左右子节点，进行preNode的next指针连接并更新。使用nextLeftNode虚拟头节点便于判断是否还有下一层并初始化preNode
class Solution {
public Node connect(Node root) {
if (root == null) return null;
Node nextLeftNode = null, currNode = root, preNode = null;
while (currNode!=null) { // 每层
nextLeftNode = new Node(0); // 下一层的虚拟头节点
preNode = nextLeftNode;
while (currNode != null) { // 遍历当前层
if(currNode.left!=null){
preNode.next=currNode.left;
preNode=preNode.next;
}
if(currNode.right!=null){
preNode.next=currNode.right;
preNode=preNode.next;
}
currNode = currNode.next;
}
currNode=nextLeftNode.next;
}
return root;
}
}（9）104. 二叉树的最大深度
①bfs+队列，同102题，每遍历一层记录一次
②dfs，递归左右节点，取层数更大的
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left,right)+1;
}
}（10）111. 二叉树的最小深度
①bfs，同102题，遇到叶子节点就返回层数
class Solution {
private Deque<TreeNode> queue;
private int res;
public int minDepth(TreeNode root) {
if(root==null)return 0;
queue = new ArrayDeque<>();
queue.addLast(root);
while(!queue.isEmpty()){
int num = queue.size();
res+=1;
for(int i=0;i<num;i++){
TreeNode temp = queue.pollFirst();
if(temp.left==null&&temp.right==null)return res;
if(temp.left!=null)queue.addLast(temp.left);
if(temp.right!=null)queue.addLast(temp.right);
}
}
return res;
}
}②dfs递归，若左右都不为零，则取最小加一，否则（即左右至少空一个）取不为零加一
class Solution {
public int minDepth(TreeNode root) {
if(root==null)return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
if(left!=0&&right!=0)return Math.min(left,right)+1;
return left!=0?left+1:right+1;
}
}二叉树篇（层序遍历）总结
①bfs+队列，可通过队列大小获取每层节点数
②dfs，递归每个节点的层数进行记录，根据题目需要设定根节点的层数为0还是1
③对于116和117题，可使用next指针进行一层遍历，同时要记录下一层位置和next连接节点
原文地址：https://blog.csdn.net/m0_70220973/article/details/140097850
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！