由两个栈互相交替存储实现

由于接下来的一层与当前层取值方向相反，当前层的最后一个节点反而是下一次要先找的节点的父亲。由此可联想到栈的特性，也就是维护两个栈，利用先进后出的特点，一个栈存储奇数层的节点，一个栈存储偶数层的节点。

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
     ArrayList<ArrayList<Integer>> res = new  ArrayList<ArrayList<Integer>>();
     if(pRoot==null) return res;
     Stack<TreeNode> stack1 = new Stack<>();
     Stack<TreeNode> stack2 = new Stack<>();
     stack1.add(pRoot);
     boolean direction =false;//f从左到右 t从右到左；
     int cnt=1;//用来计下一层的节点数
     while(cnt!=0) {//i表示当前层有多少个节点 循环的时候不断修改i的值
         cnt=0;
         ArrayList<Integer> chain = new ArrayList<Integer>();
         if(!direction) {//向右
             while(!stack1.isEmpty()) {
                 TreeNode temp=stack1.pop();
                 if(temp.left!=null) {
                     cnt++;
                     stack2.add(temp.left);
                 }
                 if(temp.right!=null) {
                     stack2.add(temp.right);
                     cnt++;
                 }
                 chain.add(temp.val); 
                  direction=true;
             }
         }else {//向左
             while(!stack2.isEmpty()) {
                 TreeNode temp=stack2.pop();
                 if(temp.right!=null) {
                     stack1.add(temp.right);
                     cnt++;
                 }
                 if(temp.left!=null) {
                     cnt++;
                     stack1.add(temp.left);
                 }
                 chain.add(temp.val);
                 direction=false;
             }         
         }           
         if(!chain.isEmpty())res.add(new ArrayList<Integer>(chain));
     }//循环结束
     return res;
}