Binary Tree Zigzag Level Order Traversal @LeetCode

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

	package leetcode.tree;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Stack;
	/**
	* Solution1: Two Stack.
	* 这边reverse 时候正好利用了stack的特性, 第一遍添加的时候，从left -> right, 读出来正好是reverse的，然后normalOrder = false,
	* 先添加right child. 再加上stack，反反为正.
	* 因为没有queue.size() 那么方便来控制level，只能用两个stack了，另外一定注意，move Depth时候，要给nextLevel新的空间，否则
	* nextLevel push的时候，currLevel指向同一空间，这样!currLevel.isEmpty.直接就全部读完了.
	*
	* Solution2: Almost same to levelOrder I. Queue + list.add(index, E);
	* Only difference is to reverse element in even number. so we use a flag here.
	* Every line, flag++, and then use % 2 to see it's odd or even level.
	*
	* @author jeffwan
	* @date Feb 12, 2014
	*/
	public class ZigzagLevelOrder {
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	if (root == null) {
	return result;
	}
	Stack<TreeNode> currLevel = new Stack<TreeNode>();
	Stack<TreeNode> nextLevel = new Stack<TreeNode>();
	currLevel.push(root);
	boolean normalOrder = true;
	while (!currLevel.isEmpty()) {
	ArrayList<Integer> level = new ArrayList<Integer>();
	while (!currLevel.isEmpty()) {
	TreeNode current = currLevel.pop();
	level.add(current.val);
	if (normalOrder) {
	if (current.left != null) {
	nextLevel.push(current.left);
	}
	if (current.right!= null) {
	nextLevel.push(current.right);
	}
	} else {
	if (current.right!= null) {
	nextLevel.push(current.right);
	}
	if (current.left != null) {
	nextLevel.push(current.left);
	}
	}
	}
	result.add(level);
	// Notice we need to give nextLevel a new space to prevent error from pointing to same space with currLevel
	currLevel = nextLevel;
	nextLevel = new Stack<TreeNode>();
	normalOrder = !normalOrder;
	}
	return result;
	}
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder2(TreeNode root) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	if (root == null) {
	return result;
	}
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	queue.offer(root);
	int flag = 1;
	while (!queue.isEmpty()) {
	ArrayList<Integer> level = new ArrayList<Integer>();
	int queueSize = queue.size();
	for (int i = 0; i < queueSize; i++) {
	TreeNode node = queue.poll();
	if (flag % 2 == 1) {
	level.add(node.val);
	} else {
	level.add(0, node.val);
	}
	if (node.left != null) {
	queue.offer(node.left);
	}
	if (node.right != null){
	queue.offer(node.right);
	}
	}
	flag++;
	result.add(level);
	}
	return result;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw ZigzagLevelOrder.java hosted with ❤ by GitHub