⼆叉树的层次遍历
转载⾃
（⼀）⼆叉树的层次遍历
  ⼆叉树的层序遍历（也叫⼴度优先遍历）的要求是：按⼆叉树的层序次序（即从根结点层⾄叶结点层），同⼀层中按先左⼦树再右⼦树的次序遍历⼆叉树。
  层次遍历的特点是，在所有未被访问结点的集合中，排列在已访问结点集合中最前⾯结点的左⼦树的根结点将最先被访问，然后是该结点的右⼦树的根结点。这样，如果把已访问的结点放在⼀个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队列实现⼆叉树的层序遍历。
  层次遍历算法如下：
  （1）初始化设置⼀个队列；
  （2）把根结点指针⼊队列；
  （3）当队列⾮空时，循环执⾏步骤（3.a-3.c）；
    （3.a）出队列取得⼀个结点指针，访问该结点；
    （3.b）若该结点的左⼦树⾮空，则将该结点的左⼦树指针⼊队列；
    （3.c）若该结点的右⼦树⾮空，则将该结点的右⼦树指针⼊队列；
  （4）结束。
二叉树的遍历及应用实验报告（⼆）从上往下打印⼆叉树
  参考：
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
/*⼆叉树的层次遍历，使⽤队列实现*/
ArrayList<Integer> res=new ArrayList<>();
if(root==null)
return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp=queue.poll();
res.add(temp.val);
if(temp.left!=null)
queue.add(temp.left);
if(temp.right!=null)
queue.add(temp.right);
}
return res;
}
}
（三）把⼆叉树打印成多⾏
  参考：
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
/*层次遍历：队列实现*/
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(pRoot==null)
return res;
Queue<TreeNode> queue=new LinkedList<>();
queue.add(pRoot);
while(!queue.isEmpty()){
ArrayList<Integer> temp=new ArrayList<>();
int len=queue.size(); //当前队列中的节点个数，也就是当前层的节点个数
for(int i=0;i<len;i++){ //依次取出这len个节点
TreeNode cur=queue.poll();
temp.add(cur.val);
if(cur.left!=null)
queue.add(cur.left);
if(cur.right!=null)
queue.add(cur.right);
}
res.add(temp);
}
return res;
}
}
（四）⼆叉树的左右视图
  ⼆叉树的左右视图就是从左边（或者右边）看⼆叉树能够看到的序列，所以其实就是每⼀层的第⼀个节点或者最后⼀个结点，本质上仍然是层序遍历。
  参考LeetCode第199题：199. Binary Tree Right Side View（题⽬难度：medium）
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res=new ArrayList<>();
if(root==null)
return res;
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int len = queue.size(); //当前队列长度，也就是当前层的节点个数
for(int i=0;i<len;i++){
TreeNode temp=queue.poll();
if(i==len-1)      //每⼀⾏最后⼀个
res.add(temp.val);
if(temp.left!=null)
queue.add(temp.left);
if(temp.right!=null)
queue.add(temp.right);
}
}
return res;
}
}
（五）之字形打印⼆叉树
  参考：
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
/*
思路：之字形打印，⽤两个栈来实现
打印奇数⾏时，将他的左右节点保存到另⼀个栈中，先左后右
打印偶数⾏时，同样将左右节点保存到栈中，先右后左
*/
ArrayList<ArrayList<Integer>> res=new ArrayList<>();
if(pRoot==null)
return res;
Stack[] stack=new Stack[2];
stack[0]=new Stack();
stack[1]=new Stack();
int num=1;
stack[1].push(pRoot);
while(!stack[0].isEmpty() || !stack[1].isEmpty()){
int cur=num%2;
ArrayList<Integer> row=new ArrayList<>();
while(!stack[cur].isEmpty()){
TreeNode temp=(TreeNode)stack[cur].pop();
row.add(temp.val);
if(cur==1){ //奇数⾏，先左再右
if(temp.left!=null)
stack[0].push(temp.left);
if(temp.right!=null)
stack[0].push(temp.right);
}else{ //偶数⾏，先右后左
if(temp.right!=null)
stack[1].push(temp.right);
if(temp.left!=null)
stack[1].push(temp.left);
}
}
res.add(row);
num++;
}
return res;
}
}
(六) ⼆叉树的层平均值
题⽬（Easy）：
题⽬描述：
给定⼀个⾮空⼆叉树, 返回⼀个由每层节点平均值组成的数组.⽰例 1:
输⼊:
3
/ \
9  20
/  \
15  7
输出: [3, 14.5, 11]
解释:
第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
解题思路：
  本题是⼆叉树层次遍历的变种。注意防⽌求和时的溢出。class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res=new ArrayList<>();
if(root==null)
return res;
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int num=queue.size();
long sum=0;  //注意防⽌溢出
for(int i=0;i<num;i++){
TreeNode temp=queue.poll();
sum+=temp.val;
if(temp.left!=null)
queue.add(temp.left);
if(temp.right!=null)
queue.add(temp.right);
}
res.add(sum*1.0/num);
}
return res;
}
}
涉及题⽬：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。