请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
例如: 给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]层序遍历 + 辅助两个栈
我们知道，层序遍历通常是采用队列作为容器来实现的。这是因为队列的特性是先进先出，符合我们按照顺序打印每层节点元素的需求。
2.1 思考1： 如果仍然使用一个队列，是否可行？
- 首先放入根节点A到队列，此时队列元素为【A】
- 根节点A出队列，为了满足第二层是逆序打印，所以我们得先把C放入队列，再把B放入队列。此时队列元素为【C，B】
- 节点C出队列，同时让子节点G和F入队；节点B出队列，同时让子节点E和D入队；此时队列元素为【G,F,E,D】。这就造成了第三层也只能是逆序打印。无法满足题目中要求的子字形打印的目的。
2.2 思考2：使用一个栈（特性是后进先出），是否可行？
- 首先放入根节点A到栈，此时栈内元素为【A】
- 栈顶元素根节点A出栈，同时将子节点B和子节点C入栈。此时栈内元素为【B, C】
- 按照后进先出，栈顶元素节点C出栈，此时将节点C的两个子节点入栈。就会造成一个问题：第三层的两个子节点入栈后，它们出栈的顺序就会在第二层的节点B前面。那么打印的顺序就会乱了。也不符合题目中的要求。
2.3 思考3：采用两个栈，是否可行？
经过2.1和2.2 的分析，普通的一个队列或者一个栈，都是无法直接满足题目要求的。
在2.2中出现的问题是，第三层的结点入栈导致第二层的结点无法及时出栈。那么如果我们采用两个栈，分别存储奇数层的节点和偶数层的节点，是否可行呢？下面我们来推演一下。
- 设置两个栈s1和s2
- 首先根节点入栈s1, 此时s1栈内元素为【A】，s2栈内元素为空。
- s1栈顶元素A出栈，同时将子节点B和子节点C 分别放入s2栈内。此时s1栈内元素为空，s2栈内元素为【B, C】。
- s2栈顶元素C出栈，同时将子节点G和子节点F分别放入s1栈内；接着，s2栈顶元素B出栈，同时将子节点E和子节点D分别放入s1栈内。此时s1栈内元素为【G, F, E, D】，s2栈内元素为空。
- …持续这个过程，直到栈s1和栈s2均为空时结束。
可见，两个栈是可行的。
复杂度分析：
- 时间复杂度：每个节点元素进栈和出栈操作各一次，时间复杂度为 O (N))
- 空间复杂度：栈 s1和栈 s2, 两个栈分别存储奇数层的节点和偶数层的节点，即存储最大容量也不超过两层节点的个数，小于 N。因此空间复杂度为 O (N))
public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
// write code here
//定义两个栈stk1，stk2；将根结点入栈stk1；
// 对于下一层，应是「从右至左」打印，因此需要遍历栈stk1、访问每一个元素，并将每一元素的孩子按照「先右孩子、后左孩子」的顺序入栈stk2；将访问的结点保存；
// 对于下一层，应是「从左至右」打印，因此需要遍历栈stk2、访问每一个元素，并将每一元素的孩子按照「先左孩子、后右孩子」的顺序入栈stk1；将访问的结点保存；
// 重复上述操作，直至两个栈全为空。
if (pRoot == null) {
return new ArrayList<>();
}
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
//存入栈
stack1.push(pRoot);
while (!stack1.isEmpty() || !stack2.isEmpty()) {
if (stack1.isEmpty()) {
res.add(print(stack2, stack1, false));
} else {
res.add(print(stack1, stack2, true));
}
}
return res;
}
//direction：打印方向，true为正向（使用saveStack保存待打印层节点时要先添加左孩子，再添加右孩子），false为反向（要先添加右孩子，再添加左孩子）
private ArrayList<Integer> print(Stack<TreeNode> popStack,
Stack<TreeNode> saveStack, boolean direction) {
ArrayList<Integer> result = new ArrayList<>();
while (!popStack.isEmpty()) {
TreeNode node = popStack.pop();
result.add(node.val);
if (direction) {
if (node.left != null) {
saveStack.add(node.left);
}
if (node.right != null) {
saveStack.add(node.right);
}
} else {
if (node.right != null) {
saveStack.add(node.right);
}
if (node.left != null) {
saveStack.add(node.left);
}
}
}
return result;
}