题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
二叉树样例
（图片来自百度百科）
按之字形打印：
F
E C
A D H G
M B
解题思路
还是基于层次遍历进行改装。如果根节点算第一层的话，那么就是奇数层从左到右，偶数层从右到左。详细的描述可以参考剑指Offer。
《剑指》里面c++语言直接定义了：
std::stack<BinaryTreeNode*> levels[2];
相当于直接定义了一个数组，数组的基础元素是栈。我按照相同的方法Java中使用，表示并不可以。
Stack<TreeNode>[] stacks = new Stack[2];
stacks[current].push(pRoot);
// 定义时候可以，但是push时候 直接会报错：
/*
Exception in thread "main" java.lang.NullPointerException
at PrintBTZigzag.Print(PrintBTZigzag.java:23)
at PrintBTZigzag.main(PrintBTZigzag.java:53)
ERROR: JDWP Unable to get JNI 1.2 environment, jvm->GetEnv() return code = -2
JDWP exit error AGENT_ERROR_NO_JNI_ENV(183): [util.c:840]
*/
题解
方案一：使用队列。这里的关键trick是 ArrayList 可以头插入或者尾插入（奇数层尾插入，偶数层头插入）。
// 队列形式 技巧有两点：
// 1. queue.size 实际上获取的是一层的结点。
// 2. 加入ArrayList时，选择头加入 或 尾加入
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if(pRoot == null) return result;
// 双端队列
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
int row = 1;
ArrayList<Integer> temp ;
while(!queue.isEmpty()){
// trick1 这个时候回去的队列的长度，实际就是当前层的所有节点数。
int size = queue.size();
temp = new ArrayList<>();
// 当前层遍历一遍
for (int i = 0; i < size; i++) {
// 去掉第一个元素
TreeNode p = queue.poll();
if (p.left!= null)
queue.offer(p.left);
if (p.right!=null)
queue.offer(p.right);
// trick 2
if (row%2==0){
// 偶数层 头插入
temp.add(0,p.val);
}
else {
// 奇数层 尾插入
temp.add(p.val);
}
}
row++;
result.add(temp);
}
return result;
}
方案二：使用两个栈，一个栈来存奇数层，一个来存偶数层。关键点在：遍历一层结束后，肯定是一个栈空，另一个栈均为下一层结点。
// 双栈的形式
public ArrayList<ArrayList<Integer>> Print2(TreeNode root){
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while(!stack1.isEmpty() || !stack2.isEmpty()){
ArrayList<Integer> temp = new ArrayList<>();
// stack1 空 那么遍历stack2 结点压入stack1
if (stack1.isEmpty()){
while(!stack2.isEmpty()) {
TreeNode p = stack2.pop();
temp.add(p.val);
// 注意压入策略 先右再左
if (p.right != null) stack1.push(p.right);
if (p.left != null) stack1.push(p.left);
}
}
// stack2 空 那么遍历stack1 结点压入stack2
else if (stack2.isEmpty()){
while(!stack1.isEmpty()) {
TreeNode p = stack1.pop();
temp.add(p.val);
// 注意压入策略 先左再有
if (p.left != null) stack2.push(p.left);
if (p.right != null) stack2.push(p.right);
}
}
result.add(temp);
}
return result;
}
