//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,null,null,15,7],

//

// 3

// / \

// 9 20

// / \

// 15 7

//

//

//

//return its zigzag level order traversal as:

//

//[

// [3],

// [20,9],

// [15,7]

//]

//

//

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

package com.llz.algorithm.algorithm2019.secondweek;

import java.util.*;

import com.llz.algorithm.algorithm2019.firstweek.TreeNode;

public class LeetCode_103_2 {

/**

* Original version

* Time complexity is O(n), space complexity is O(n)

*

* @param root

* @return

*/

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

List<List<Integer>> list = new ArrayList<>();

if (root == null) return list;

Deque<TreeNode> queue = new ArrayDeque<>();

Deque<TreeNode> innerQueue = new ArrayDeque<>();

queue.add(root);

List<Integer> innerList = new ArrayList<>();

innerList.add(root.val);

list.add(innerList);

int size = 0;

boolean leftToRight = false;

TreeNode temp = null;

while (!queue.isEmpty()) {

size = queue.size();

innerList = new ArrayList<>();

for (int i = 0; i < size; i++) {

temp = queue.removeLast();

if (leftToRight) {

if (temp.left != null) {

innerQueue.add(temp.left);

innerList.add(temp.left.val);

}

if (temp.right != null) {

innerQueue.add(temp.right);

innerList.add(temp.right.val);

}

} else {

if (temp.right != null) {

innerQueue.add(temp.right);

innerList.add(temp.right.val);

}

if (temp.left != null) {

innerQueue.add(temp.left);

innerList.add(temp.left.val);

}

}

}

if (innerList.size() != 0)

list.add(innerList);

queue = innerQueue;

innerQueue = new ArrayDeque<>();

leftToRight = leftToRight == true ? false : true;

}

return list;

}

/**

* A more cleaner and easier code referenced from discussion

* with only one queue compared with two queues that used by my original version.

* Remember better utilize JDK API, think about using list.add(index, val) instead of construct an stack.

* Time complexity is O(n) and space complexity is O(n) as well.

*

* @param root

* @return

*/

public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {

List<List<Integer>> res = new ArrayList<>();

if (root == null) return res;

boolean leftToRight = false;

Queue<TreeNode> queue = new ArrayDeque<>();

List<Integer> list = new ArrayList<>();

queue.add(root);

while (!queue.isEmpty()) {

int size = queue.size();

for (int i = 0; i < size; i++) {

TreeNode temp = queue.remove();

if (leftToRight)

list.add(0, temp.val);

else

list.add(temp.val);

if (temp.left != null)

queue.add(temp.left);

if (temp.right != null)

queue.add(temp.right);

}

leftToRight = !leftToRight;

res.add(list);

list = new ArrayList<>();

}

return res;

}

public static void main(String[] args) {

TreeNode root = new TreeNode(1);

root.left = new TreeNode(2);

root.right = new TreeNode(3);

root.left.left = new TreeNode(4);

root.left.right = new TreeNode(5);

root.right.left = new TreeNode(6);

root.right.right = new TreeNode(7);

root.left.left.left = new TreeNode(8);

root.left.right.left = new TreeNode(9);

root.right.right.left = new TreeNode(10);

LeetCode_103_2 lc = new LeetCode_103_2();

List<List<Integer>> list = lc.zigzagLevelOrder2(root);

System.out.println(list);

}

}