Binary Tree Zigzag Level Order Traversal (Java)

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]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

	"Time Complexity is O(n)"
	"Take advantage of two stack"
	"one is used hold current level's node another is used to hold next level's hold,"
	"moreover there is flag used to mark the sequece (left to rigth or right to left)"
	"put the root first into curretn stack then pop it out, put left and right into next_level stack (pay attention to sequence)"
	"once current stack is empty swap current and next level, level ++, reverse sequence"
	// rewrite at 2/7/2014
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>> ();
	if (root==null ){
	return result;
	}
	boolean leftToRight=true;
	Stack<TreeNode> current=new Stack<TreeNode>();
	Stack<TreeNode> next=new Stack<TreeNode>();
	current.push(root);
	int level=0;
	while (!current.isEmpty()){
	if (result.size()==level){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	result.add(temp);
	}
	TreeNode currentNode=current.pop();
	result.get(level).add(currentNode.val);
	if (leftToRight){
	if (currentNode.left!=null) next.push(currentNode.left);
	if (currentNode.right!=null) next.push(currentNode.right);
	}
	else{
	if (currentNode.right!=null) next.push(currentNode.right);
	if (currentNode.left!=null) next.push(currentNode.left);
	}
	// current level is empty, swap current level and next level
	// reverse boolean leftToRight
	// level++;
	if (current.isEmpty()){
	level++;
	leftToRight=!leftToRight;
	Stack<TreeNode> temp=current;
	current=next;
	next=temp;
	}
	}
	return result;
	}
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	import java.util.*;
	public class Solution {
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
	Stack<TreeNode> current_level =new Stack<TreeNode> ();
	Stack<TreeNode> next_level=new Stack<TreeNode>();
	boolean leftToright=false;
	int level=0;
	if (root!=null){
	current_level.push(root);
	while(!current_level.isEmpty()){
	TreeNode current=current_level.pop();
	addToarraylist(result, current.val,level);
	if (leftToright){
	if (current.right!=null){
	next_level.push(current.right);
	}
	if (current.left!=null){
	next_level.push(current.left);
	}
	}
	else{
	if (current.left!=null){
	next_level.push(current.left);
	}
	if (current.right!=null){
	next_level.push(current.right);
	}
	}
	if (current_level.isEmpty()){
	Stack<TreeNode> temp=current_level;
	current_level=next_level;
	next_level=temp;
	level++;
	leftToright=!leftToright;
	}
	}
	}
	return result;
	}
	public void addToarraylist(ArrayList<ArrayList<Integer>> result,int value, int level){
	if (level==result.size()){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	temp.add(value);
	result.add(temp);
	}
	else{
	ArrayList<Integer> temp=result.get(level);
	temp.add(value);
	}
	}
	}

view raw BinaryTreeZigzagLevelOrderTraversal.java hosted with ❤ by GitHub