import java.util.ArrayList;
import java.util.ArrayDeque;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> Arr = new ArrayList<ArrayList<Integer>>();
if(pRoot==null)
return Arr;
//层序遍历,想到队列
ArrayDeque<TreeNode> dq = new ArrayDeque<>();
dq.addLast(pRoot);
int layer=1;//记录当前遍历的层数,奇数层从左到右遍历,偶数层反之
while(!dq.isEmpty()){
int curSize = dq.size();//当前层的节点个数
ArrayList<Integer> arr = new ArrayList<Integer>();
if((layer++)%2==1){
while(curSize-->0){
TreeNode node = dq.pollFirst(); //从队列头出节点
arr.add(node.val);
//在队列尾添加节点,先添加左节点,再添加右节点
if(node.left!=null) dq.addLast(node.left);
if(node.right!=null) dq.addLast(node.right);
}
} else {
while(curSize-->0){
TreeNode node = dq.pollLast();//从队列尾出节点
arr.add(node.val);
//在队列头添加节点,因为新节点添加后原来的节点会往后移,
//所以需要先添加右节点,再添加左节点
if(node.right!=null) dq.addFirst(node.right);
if(node.left!=null) dq.addFirst(node.left);
}
}
Arr.add(arr);
}
return Arr;
}
}