My AC Java code
I use two stacks, one for processing current layer and one for storing nodes for the next layer. I also use a flag (order in your code) to indicate the directio
I use two stacks, one for processing current layer and one for storing nodes for the next layer. I also use a flag (order in your code) to indicate the direction. It is straightforward\n\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> output = new ArrayList<List<Integer>>();\n        if (root == null) return output;\n        Stack<TreeNode> cur_layer = new Stack<TreeNode>(); cur_layer.push(root);\n        Stack<TreeNode> next_layer = new Stack<TreeNode>();\n        List<Integer> layer_output = new ArrayList<Integer>();\n        int d = 0; // 0: left to right; 1: right to left.\n        \n        while (!cur_layer.isEmpty()){\n        \tTreeNode node = cur_layer.pop();\n        \tlayer_output.add(node.val);\n        \tif(d==0){\n        \t\tif (node.left != null) next_layer.push(node.left);\n        \t\tif (node.right != null) next_layer.push(node.right);\n        \t}else{\n        \t\tif (node.right != null) next_layer.push(node.right);\n        \t\tif (node.left != null) next_layer.push(node.left);\n        \t}\n        \t\n        \tif (cur_layer.isEmpty()){\n        \t\toutput.add(layer_output);\n        \t\tlayer_output = new ArrayList<Integer>();\n        \t\tcur_layer = next_layer;\n        \t\tnext_layer = new Stack<TreeNode>();;\n        \t\td ^= 1;\n        \t}\n        }\n        return output;\n    }
[]