107. 二叉树的层序遍历 II
相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。
class Solution {
//利用链表可以进行o(1)头部插入
public LinkedList<List<Integer>> res = new LinkedList<List<Integer>>();
public List<List<Integer>> levelOrderBottom(TreeNode root) {
/*
order(root);
List<List<Integer>> resBottom = new ArrayList<List<Integer>>();
for(int i = res.size()-1;i>=0;i--){
resBottom.add(res.get(i));
}
return resBottom;
*/
order(root);
return res;
}
//BFS-迭代法，使用队列
public void order(TreeNode node){
if(node == null){
return;
}
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while(!que.isEmpty()){
List<Integer> list = new ArrayList<Integer>();
int deep = que.size();
while(deep> 0){
TreeNode cur = que.poll();
list.add(cur.val);
if(cur.left!=null){
que.offer(cur.left);
}
if(cur.right!=null){
que.offer(cur.right);
}
deep--;
}
//res.add(list);
//插入到头部，满足层次返序
res.addFirst(list);
}
}
}
199. 二叉树的右视图
层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
class Solution {
public List<Integer> res = new ArrayList<Integer>();
public List<Integer> rightSideView(TreeNode root) {
//队列 迭代
//每次返回每层的最后一个字段即可
order(root);
return res;
}
public void order(TreeNode node){
if(node == null){
return;
}
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while(!que.isEmpty()){
int deep = que.size();
for(int i=1;i<=deep;i++){
TreeNode cur = que.poll();
if(cur.left!=null){
que.offer(cur.left);
}
if(cur.right!=null){
que.offer(cur.right);
}
//每层队列中最后的即最右边的
if(i == deep){
res.add(cur.val);
}
}
}
}
}
637. 二叉树的层平均值
本题就是层序遍历的时候把一层求个总和在取一个均值。
class Solution {
public List<Double> res = new ArrayList<Double>();
public List<Double> averageOfLevels(TreeNode root) {
order(root);
return res;
}
public void order(TreeNode node){
if(node == null){
return;
}
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while(!que.isEmpty()){
int deep = que.size();
double levelSum = 0.0;
for(int i=1;i<=deep;i++){
TreeNode cur = que.poll();
levelSum +=cur.val;
if(cur.left!=null){
que.offer(cur.left);
}
if(cur.right!=null){
que.offer(cur.right);
}
}
res.add(levelSum / deep);
}
}
}
429. N 叉树的层序遍历
这道题依旧是模板题，只不过一个节点有多个孩子了
class Solution {
public List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(Node root) {
order(root);
return res;
}
public void order(Node node){
if(node == null){
return;
}
Queue<Node> que = new LinkedList<Node>();
que.offer(node);
while(!que.isEmpty()){
List<Integer> list = new ArrayList<Integer>();
int deep = que.size();
for(int i =0;i<deep;i++){
//N叉数的Node
Node cur = que.poll();
list.add(cur.val);
//获取N叉数的孩子
List<Node> children = cur.children;
//判空都加进队列
if(children == null || children.size() == 0){
continue;
}
for(Node child : children){
if(child != null){
que.offer(child);
}
}
}
res.add(list);
}
}
}
515. 在每个树行中找最大值
层序遍历，取每一层的最大值
class Solution {
public List<Integer> res = new ArrayList<>();
public List<Integer> largestValues(TreeNode root) {
order(root);
return res;
}
public void order(TreeNode node){
if(node == null){
return;
}
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while(!que.isEmpty()){
int deep = que.size();
int max = Integer.MIN_VALUE;
for(int i = 0;i< deep;i++){
TreeNode cur = que.poll();
max = Math.max(max,cur.val);
if(cur.left!=null){
que.offer(cur.left);
}
if(cur.right!=null){
que.offer(cur.right);
}
}
res.add(max);
}
}
}
116. 填充每个节点的下一个右侧节点指针
本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了
class Solution {
public Node connect(Node root) {
if(root==null) {return null;}
if(root.left != null){
root.left.next = root.right;
if(root.next != null){
root.right.next = root.next.left;
}
connect(root.left);
connect(root.right);
}
return root;
}
}
117. 填充每个节点的下一个右侧节点指针 II
这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道
class Solution {
public Node connect(Node root) {
return order(root);
}
public Node order(Node node){
if(node == null){
return null;
}
Queue<Node> que = new LinkedList<Node>();
que.offer(node);
while(!que.isEmpty()){
int deep = que.size();
Node cur = new Node();
Node next = new Node();
for(int i =0;i<deep;i++){
if(i==0){//取出一层头结点
cur = que.poll();
//把当前层头结点视为 next节点，以便操作左右节点入队列
next = cur;
}else{
next = que.poll();
//本层前一个节点next指向本节点
cur.next = next;
//当前视角cur 应为next节点，以便连接下个，没有了就连最后的NULL
cur = next;
}
if(next.left!=null){
que.offer(next.left);
}
if(next.right!=null){
que.offer(next.right);
}
}
//本层最后一个节点指NULL
cur.next = null;
}
return node;
}
}
104. 二叉树的最大深度
使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。
在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度
class Solution {
int depth = 0;
int res=0;
public int maxDepth(TreeNode root){
//traverse(root);
return order(root);
}
public int order(TreeNode node){
if(node == null){
return 0;
}
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
//深度计数器
int len = 0;
while(!que.isEmpty()){
int deep = que.size();
while(deep> 0){
TreeNode cur = que.poll();
if(cur.left!=null){
que.offer(cur.left);
}
if(cur.right!=null){
que.offer(cur.right);
}
deep--;
}
//深度累加
len++;
}
return len;
}
void traverse(TreeNode root){
if(root == null){
return;
}
depth++;
res=Math.max(res,depth);
traverse(root.left);
traverse(root.right);
depth--;
}
}
111. 二叉树的最小深度
相对于 104.二叉树的最大深度 ，本题还也可以使用层序遍历的方式来解决，思路是一样的。
需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点
class Solution {
public int minDepth(TreeNode root) {
//return order(root);
return reCurSion(root);
}
private int reCurSion(TreeNode node){
if(node == null){return 0;}
int leftDepth = reCurSion(node.left);
int rightDepth = reCurSion(node.right);
if(node.left==null){
return rightDepth+1;
}
if(node.right == null){
return leftDepth+1;
}
return Math.min(leftDepth,rightDepth)+1;
}
public int order(TreeNode node){
if(node == null){
return 0;
}
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
//可操作
int len=0;
while(!que.isEmpty()){
int deep = que.size();
//最小深度赋值
len++;
for(int i=0; i<deep; i++){
TreeNode cur = que.poll();
//如果当前节点的左右孩子都为空，直接返回最小深度
if(cur.left ==null && cur.right == null){
return len;
}
if(cur.left!=null){
que.offer(cur.left);
}
if(cur.right!=null){
que.offer(cur.right);
}
}
//可操作
}
return len;
}
}