题解 | #按之字形顺序打印二叉树#
按之字形顺序打印二叉树
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
import java.util.*;
import java.util.ArrayList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
Stack<Integer> s=new Stack<Integer>();
Queue<TreeNode> q_l=new ArrayDeque<TreeNode>();//上一层的队列
Queue<TreeNode> q_n=new ArrayDeque<TreeNode>();//下一层的队列
ArrayList<Integer> arr1=new ArrayList<Integer>();
ArrayList<ArrayList<Integer> > arr2=new ArrayList<ArrayList<Integer> >();
boolean flag_ceng=false;
if(pRoot==null)
return arr2;
q_l.offer(pRoot);//添加头节点
while(true)
{
pRoot=q_l.poll();//弹出队列元素
arr1.add(pRoot.val);
if(pRoot.left!=null)
q_n.offer(pRoot.left);//添加左节点
if(pRoot.right!=null)
q_n.offer(pRoot.right);//添加左节点
if(q_l.isEmpty()==true)//上一次的队列弹出完成
{
if(flag_ceng)//当为偶数层,反转
Collections.reverse(arr1);
arr2.add(arr1);
if(q_n.isEmpty()==true)//当此次循环也无填充时
break;
q_l=q_n;//将上一层用下一层替换
flag_ceng=!flag_ceng;
q_n=new ArrayDeque<TreeNode>();//清空下一层队列,用于后续填充
arr1=new ArrayList<Integer>();
//arr1.clear();//清空每一层arr
}
}
return arr2;
}
}
import java.util.ArrayList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
Stack<Integer> s=new Stack<Integer>();
Queue<TreeNode> q_l=new ArrayDeque<TreeNode>();//上一层的队列
Queue<TreeNode> q_n=new ArrayDeque<TreeNode>();//下一层的队列
ArrayList<Integer> arr1=new ArrayList<Integer>();
ArrayList<ArrayList<Integer> > arr2=new ArrayList<ArrayList<Integer> >();
boolean flag_ceng=false;
if(pRoot==null)
return arr2;
q_l.offer(pRoot);//添加头节点
while(true)
{
pRoot=q_l.poll();//弹出队列元素
arr1.add(pRoot.val);
if(pRoot.left!=null)
q_n.offer(pRoot.left);//添加左节点
if(pRoot.right!=null)
q_n.offer(pRoot.right);//添加左节点
if(q_l.isEmpty()==true)//上一次的队列弹出完成
{
if(flag_ceng)//当为偶数层,反转
Collections.reverse(arr1);
arr2.add(arr1);
if(q_n.isEmpty()==true)//当此次循环也无填充时
break;
q_l=q_n;//将上一层用下一层替换
flag_ceng=!flag_ceng;
q_n=new ArrayDeque<TreeNode>();//清空下一层队列,用于后续填充
arr1=new ArrayList<Integer>();
//arr1.clear();//清空每一层arr
}
}
return arr2;
}
}