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

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) {
        //特殊值(空指针)处理
        if(pRoot == null){
            return new ArrayList<ArrayList<Integer>>();
        }
        
        ArrayList<ArrayList<Integer>> array = new ArrayList<ArrayList<Integer> >();//创建一个链表
        Stack<TreeNode> stack1 = new Stack<>();//创建一个栈1，栈1存放二叉树的奇数层节点
        Stack<TreeNode> stack2 = new Stack<>();//创建一个栈2，栈2存放二叉树的偶数层节点
        stack1.push(pRoot);//将根节点压入栈1
        //遍历二叉树
        while(stack1.empty() == false || stack2.empty() == false){
            ArrayList<Integer> arr = new ArrayList<>();
            //遍历栈1，将栈1中的节点的儿子节点从左向右压入栈2
            while(!stack1.empty()){
                TreeNode treeNode = stack1.pop();//从栈1中弹出头结点
                arr.add(treeNode.val);//将遍历栈1的元素节点的值添加到临时链表中
                //将栈1中的节点的儿子节点从左向右压入栈2
                if(treeNode.left != null){//先压入左儿子节点
                    stack2.push(treeNode.left);
                }
                if(treeNode.right != null){//后压入右儿子节点
                    stack2.push(treeNode.right);
                }
            }
            //每遍历一次栈，都要将临时链表压入链表中
            if(arr.size() != 0){
                array.add(arr);
                continue;//栈1和栈2不可能同时有值
            }
            //遍历栈2，将栈2中的节点的儿子节点从右向左压入栈1
            while(!stack2.empty()){
                TreeNode treeNode = stack2.pop();//从栈2中弹出头结点
                arr.add(treeNode.val);//将遍历栈1的元素节点的值添加到临时链表中
                //将栈2中的节点的儿子节点从右向左压入栈2
                if(treeNode.right != null){//先压入右儿子节点
                    stack1.push(treeNode.right);
                }
                if(treeNode.left != null){//后压入左儿子节点
                    stack1.push(treeNode.left);
                }
            }
            array.add(arr);//每遍历一次栈，都要将临时链表压入链表中
        }
        
        
        return array;
    }

}