双栈解法

题目要求按照之字形输出结果， 但是在二叉树里，层序遍历用的是队列，而且是固定从左到右输出； 而前中后序都不满足题目要求，观察发现，之字形和层序遍历的区别，

在于：层序队列用的队列来存结点，先存什么就先出什么，而之字形要求顺序反过来，这里自然地想到了栈，先进后出。 继续观察发现，发现后续结点的遍历，需要根据遍历的方向，来决定先存左孩子还是右孩子，假如当前是从右往左遍历，那么需要先存右孩子，再存左孩子；反之需要先存左孩子再存右孩子。

思路：分成两个栈：从左往右遍历的栈，和从右向左遍历的栈；或者可以理解成先存左右孩子的哪个节点的栈。声明好两个栈之后，就是只要两个栈都不为空，说明有树还没遍历完，可以继续遍历。那么按照上面分析的方式去存相应的结点即可。

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>> res = new ArrayList<>();
        if(pRoot == null){
            return res;
        }
        //先存左孩子还是右孩子
        Stack<TreeNode> left = new Stack<>();
        Stack<TreeNode> right = new Stack<>();
        TreeNode temp;
        right.push(pRoot);
        while(!left.empty() || !right.empty()){
            ArrayList<Integer> list = new ArrayList<>();
            while(!left.empty()){
                temp = left.pop();
                if(temp.right != null){
                    right.push(temp.right);
                }
                if(temp.left != null){
                    right.push(temp.left);
                }
                list.add(temp.val);
            }
            if(list.size() > 0){
                res.add(list);
                continue;
            }
            while(!right.empty()){
                temp = right.pop();
                if(temp.left != null){
                    left.push(temp.left);
                }
                if(temp.right != null){
                    left.push(temp.right);
                }
                list.add(temp.val);
            }
            res.add(list);
        }
        return res;
    }

}