力扣labuladong——一刷day64

本文主要是介绍力扣labuladong——一刷day64，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、力扣515. 在每个树行中找最大值
二、力扣637. 二叉树的层平均值
三、力扣958. 二叉树的完全性检验

前言

二叉树大部分题目都可以用递归的算法解决，但少部分题目用递归比较麻烦的话，我们可以考虑使用层序遍历的方式解决。

一、力扣515. 在每个树行中找最大值

/*** 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 List<Integer> largestValues(TreeNode root) {List<Integer> res = new ArrayList<>();if(root == null){return res;}Deque<TreeNode> deq = new ArrayDeque<>();deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();int max = Integer.MIN_VALUE;for(int i = 0; i < size; i ++){TreeNode cur = deq.pollFirst();if(cur.left != null){deq.offerLast(cur.left);}if(cur.right != null){deq.offerLast(cur.right);}max = Math.max(max, cur.val);}res.add(max);}return res;}
}

二、力扣637. 二叉树的层平均值

/*** 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 List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();if(root == null){return res;}Deque<TreeNode> deq = new ArrayDeque<>();deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();double sum = 0;for(int i = 0; i < size; i ++){TreeNode cur = deq.pollFirst();if(cur.left != null){deq.offerLast(cur.left);}if(cur.right != null){deq.offerLast(cur.right);}sum += cur.val;}res.add(sum / size);}return res;}
}

三、力扣958. 二叉树的完全性检验

/*** 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 {class Pair{TreeNode node;int id;public Pair(TreeNode node,int id){this.node = node;this.id = id;}}public boolean isCompleteTree(TreeNode root) {if(root == null){return true;}Deque<Pair> deq = new ArrayDeque<>();deq.offerLast(new Pair(root,1));int flag = 1;while(!deq.isEmpty()){int size = deq.size();for(int i = 0; i < size; i ++){Pair cur = deq.pollFirst();TreeNode curNode = cur.node;int curId = cur.id;if(curId != flag){return false;}if(curNode.left != null){deq.offerLast(new Pair(curNode.left,curId*2));}if(curNode.right != null){deq.offerLast(new Pair(curNode.right,curId*2+1));}flag ++;}}return true;}
}