题解 | #按之字形顺序打印二叉树#

import java.util.ArrayList;

/*
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<ArrayList<Integer>>();
        if(pRoot==null) return res;
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        stack1.push(pRoot);
        while(!stack1.empty()||!stack2.empty()){
            ArrayList<Integer> level1=new ArrayList<>();
            ArrayList<Integer> level2=new ArrayList<>();
            while(!stack1.empty()){
                //如果stack1不为空，说明奇数行不为空，所以要把把它的左右结点放偶数行栈2
                if(stack1.peek().left!=null) stack2.push(stack1.peek().left);
                if(stack1.peek().right!=null) stack2.push(stack1.peek().right);
                level1.add(stack1.pop().val);
            }
            while(!stack2.empty()){
                //如果stack2不为空，说明偶数行不为空，所以要把把它的右左结点放奇数行栈1
                if(stack2.peek().right!=null) stack1.push(stack2.peek().right);
                if(stack2.peek().left!=null) stack1.push(stack2.peek().left);
                level2.add(stack2.pop().val);
            }
            if(!level1.isEmpty()) res.add(level1);
            if(!level2.isEmpty()) res.add(level2);
        }
        return res;
    }

}