按之字形顺序打印二叉树

思路：其实就是树的广度遍历，不过每一层要进行一次反向即可。当然可以用queue来做，也可以通过计算树每个节点所在高度来选择是否反转此层。而我这里是通过两个栈来实现的，不需要计算高度，也不需要用标记来标记哪一层需要反转：
这个办法我写起来其实蛮麻烦的，相信有更简单的代码能实现这个思路。

import java.util.*;
/*
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) {
        Stack<TreeNode> stack1 = new Stack<TreeNode>();//遍历奇数层
        Stack<TreeNode> stack2 = new Stack<TreeNode>();//遍历偶数层
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(pRoot == null){
            return results;
        }
        stack1.push(pRoot);
        while(stack1.size()!=0 || stack2.size()!=0){
            if(stack1.size()!=0){//stack1不为空，就一直出栈，并把左右子压入stack2
                TreeNode node = stack1.peek();
                if(node.left!=null){
                    stack2.push(node.left);//先入左再入右，则根据stack会反向
                }
                if(node.right!=null){
                    stack2.push(node.right);
                }
                result.add(stack1.pop().val);//将出栈的节点记录到result中
                if(stack1.size()==0){//当栈出完，那么就将result记录到results中
                    //注意，因为result要重用，故这里定义一个currentResult来保留result中的值
                    ArrayList<Integer> currentResult = new ArrayList<Integer>();
                    for(int i=0;i<result.size();i++) {
                        currentResult.add(result.get(i));
                    }
                    results.add(currentResult);
                    while(result.size()>0){//将result值清空，供下一层重用
                        result.remove(0);
                    }
                }
            }else{//stack2.size()!=0
                while(true) {//用while是为了防止stack2栈没出完就又去出stack1栈了
                    TreeNode node = stack2.peek();
                    if(node.right!=null){
                        stack1.push(node.right);//先右后左，再次反向
                    }
                    if(node.left!=null){
                        stack1.push(node.left);
                    }
                    result.add(stack2.pop().val);
                    if(stack2.size()==0){//出完栈，则记录值，并且break这个while循环，换到stack1进行出栈
                        ArrayList<Integer> currentResult = new ArrayList<Integer>();
                        for(int i=0;i<result.size();i++) {
                            currentResult.add(result.get(i));
                        }
                        results.add(currentResult);
                        while(result.size()>0){
                            result.remove(0);
                        }
                        break;
                    }
                }
            }
        }
        return results;
    }

}