题目
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
分析
如图的二叉树：
按照题目的要求输出的结果是：
1
3 2
4 5 6 7
15 14 13 12 11 10 9 8
可以发现奇数行是按照从左往右的顺序输出的，偶数行是按照从右往左的顺序输出的。
这点就有点类似树的层序遍历。
那么，我们在遍历每一层的时候，用一个容器去按一定的顺序存储节点，然后将这个容器最终加入到题目要求返回的ArrayList<ArrayList
这里我们选用栈去存储，当我们遍历第一层的时候，将节点按照左孩子到右孩子的顺序加入栈，这样出栈的顺序就是从右往左，先输入右孩子，再输出左孩子。
这样，我们可以总结一个规律：
基数行：按照从左往右输出，那么添加的时候就要从右往左添加，偶数行恰好是反的
代码
import java.util.ArrayList;
import java.util.Stack;
/*
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) {
ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();
if (pRoot == null) {
return resultList;
}
// 创建两个栈，分别用于存储奇数和偶数行的元素
Stack <TreeNode>oddStack = new Stack<>();
Stack <TreeNode>evenStack = new Stack<>();
// 根节点加入到奇数行
oddStack.add(pRoot);
// 奇数和偶数行的标志位
boolean isOdd = true;
// 循环读取奇数和偶数行的每个节点的孩子节点，按对应的顺序装入到list
while (oddStack.size() > 0 || evenStack.size() > 0) {
// 临时存储某一行节点的list
ArrayList<Integer> tempList = new ArrayList<>();
if (isOdd == true) {// 当前节点处于基数行
// 当前节点是基数行，那么存储他的孩子节点就要才从右往左
while(oddStack.size() > 0){
TreeNode currentNode = oddStack.peek(); // 取出当前的栈顶节点，但是不弹出
tempList.add(currentNode.val);
if (currentNode.left != null) {
evenStack.add(currentNode.left);
}
if (currentNode.right != null) {
evenStack.add(currentNode.right);
}
// 弹出栈顶元素
oddStack.pop();
}
resultList.add(tempList);
isOdd = !isOdd;
}else {
while (evenStack.size() > 0) {
TreeNode currentNode = evenStack.peek();
tempList.add(currentNode.val);
if (currentNode.right != null) {
oddStack.add(currentNode.right);
}
if (currentNode.left != null) {
oddStack.add(currentNode.left);
}
evenStack.pop();
}
resultList.add(tempList);
isOdd = !isOdd;
}
}
return resultList;
}
}
