二叉树的之字形层序遍历

import java.util.*;




public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public static ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        while (stack1.size() != 0 || stack2.size() != 0){
            ArrayList<Integer> item = new ArrayList<>();
            if (stack1.isEmpty()){
                while (!stack2.isEmpty()){
                    TreeNode node = stack2.pop();
                    item.add(node.val);
                    if (node.right != null){
                        stack1.add(node.right);
                    }
                    if (node.left != null){
                        stack1.add(node.left);
                    }
                }
                list.add(item);
            }else {
                while (!stack1.isEmpty()){
                    TreeNode node = stack1.pop();
                    item.add(node.val);
                    if (node.left != null){
                        stack2.add(node.left);
                    }
                    if (node.right != null){
                        stack2.add(node.right);
                    }
                }
                list.add(item);
            }
        }
        return list;
    }


}