【剑指offer】按之字形顺序打印二叉树

很巧的思路，佩服佩服~
用两个栈进行维护，当前层次的节点放到栈1里，下一层次的节点放到栈2里。

声明：层次遍历二叉树，然后对偶数层进行反转，复杂度也是O(n)。和上面用两个栈维护的复杂度是同一个级别，并没有本质的区别，只是上面思路O(n)的系数小一丢丢，还有上面思路比较不好想，很巧妙。

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if (pRoot == null) {
            return list;
        }
        ArrayList<Integer> lineList;
        stack1.push(pRoot);
        while (!stack1.empty()) {
            lineList = new ArrayList<>();
            while (!stack1.empty()) {
                TreeNode treeNode = stack1.peek();
                stack1.pop();
                lineList.add(treeNode.val);
                if (treeNode.left != null) {
                    stack2.push(treeNode.left);
                }
                if (treeNode.right != null) {
                    stack2.push(treeNode.right);
                }
            }
            list.add(lineList);

            if (!stack2.empty()) {
                lineList = new ArrayList<>();
                while (!stack2.empty()) {
                    TreeNode treeNode = stack2.peek();
                    stack2.pop();
                    lineList.add(treeNode.val);
                    if (treeNode.right != null) {
                        stack1.push(treeNode.right);
                    }
                    if (treeNode.left != null) {
                        stack1.push(treeNode.left);
                    }
                }
                list.add(lineList);
            }
        }
        return list;
    }
}