1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 12, 2015
4+ Problem: Binary Tree Zigzag Level Order Traversal
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
7+ Notes:
8+ Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left
9+ to right, then right to left for the next level and alternate between).
10+ For example:
11+ Given binary tree {3,9,20,#,#,15,7},
12+ 3
13+ / \
14+ 9 20
15+ / \
16+ 15 7
17+ return its zigzag level order traversal as:
18+ [
19+ [3],
20+ [20,9],
21+ [15,7]
22+ ]
23+
24+ Solution: 1. Queue + reverse.
25+ 2. Two stacks.
26+ */
27+
28+ /**
29+ * Definition for binary tree
30+ * public class TreeNode {
31+ * int val;
32+ * TreeNode left;
33+ * TreeNode right;
34+ * TreeNode(int x) { val = x; }
35+ * }
36+ */
37+ public class Solution {
38+ public List <List <Integer >>zigzagLevelOrder_1 (TreeNode root ) {
39+ List <List <Integer >>res =new ArrayList <List <Integer >>();
40+ if (root ==null )return res ;
41+ Queue <TreeNode >q =new LinkedList <TreeNode >();
42+ q .offer (root );
43+ q .offer (null );
44+ List <Integer >level =new ArrayList <Integer >();
45+ int depth =0 ;
46+ while (true ) {
47+ TreeNode node =q .poll ();
48+ if (node !=null ) {
49+ level .add (node .val );
50+ if (node .left !=null )q .offer (node .left );
51+ if (node .right !=null )q .offer (node .right );
52+ }else {
53+ if (depth %2 ==1 )Collections .reverse (level );
54+ res .add (level );
55+ depth ++;
56+ level =new ArrayList <Integer >();
57+ if (q .isEmpty ()==true )break ;
58+ q .offer (null );
59+ }
60+ }
61+ return res ;
62+ }
63+ public List <List <Integer >>zigzagLevelOrder (TreeNode root ) {
64+ List <List <Integer >>res =new ArrayList <List <Integer >>();
65+ if (root ==null )return res ;
66+ Stack <TreeNode >cur =new Stack <TreeNode >();
67+ Stack <TreeNode >last =new Stack <TreeNode >();
68+ boolean left2right =true ;
69+ last .push (root );
70+ List <Integer >level =new ArrayList <Integer >();
71+ while (last .empty () ==false ) {
72+ TreeNode node =last .pop ();
73+ if (node !=null ) {
74+ level .add (node .val );
75+ if (left2right ) {
76+ if (node .left !=null )cur .push (node .left );
77+ if (node .right !=null )cur .push (node .right );
78+ }else {
79+ if (node .right !=null )cur .push (node .right );
80+ if (node .left !=null )cur .push (node .left );
81+ }
82+ }
83+ if (last .empty () ==true ) {
84+ if (level .size () !=0 )
85+ res .add (level );
86+ level =new ArrayList <Integer >();
87+ Stack <TreeNode >temp =last ;
88+ last =cur ;
89+ cur =temp ;
90+ left2right = !left2right ;
91+ }
92+ }
93+ return res ;
94+ }
95+ }
