题解 | #二叉树的之字形层序遍历#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
         // write code here
        if(root == null){
            return new ArrayList<ArrayList<Integer>>();
        }else{
            Stack<TreeNode> stack1 = new Stack<TreeNode>();
            Stack<TreeNode> stack2 = new Stack<TreeNode>();
            ArrayList<ArrayList<Integer>> arrOutside = new ArrayList<ArrayList<Integer>>();

            stack2.add(root);
            while(!stack1.isEmpty() || !stack2.isEmpty() ){
                ArrayList<Integer> arrInside1 = new ArrayList<Integer>();
                while(!stack1.isEmpty()){
                    TreeNode cur = stack1.pop();
                    arrInside1.add(cur.val);
                    if(cur.right != null){
                        stack2.push(cur.right);
                    }
                    if(cur.left != null){
                        stack2.push(cur.left);
                    }
                }
                if(!arrInside1.isEmpty()){
                    arrOutside.add(arrInside1);
                }
                ArrayList<Integer> arrInside2 = new ArrayList<Integer>();
                while(!stack2.isEmpty()){
                    TreeNode cur = stack2.pop();
                    arrInside2.add(cur.val);
                    if(cur.left != null){
                        stack1.push(cur.left);
                    }
                    if(cur.right != null){
                        stack1.push(cur.right);
                    }
                }
                if(!arrInside2.isEmpty()){
                    arrOutside.add(arrInside2);
                }
            }
            return arrOutside;
        }
    }
}