* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
* @param root: A Tree
* @return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
*/
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
Stack<TreeNode> currLevel = new Stack<TreeNode>();
Stack<TreeNode> nextLevel = new Stack<TreeNode>();
Stack<TreeNode> tmp;
currLevel.push(root);
boolean normalOrder = true;
while (!currLevel.isEmpty()) {
ArrayList<Integer> currLevelResult = new ArrayList<Integer>();
while (!currLevel.isEmpty()) {
TreeNode node = currLevel.pop();
currLevelResult.add(node.val);
if (normalOrder) {
if (node.left != null) {
nextLevel.push(node.left);
}
if (node.right != null) {
nextLevel.push(node.right);
}
} else {
if (node.right != null) {
nextLevel.push(node.right);
}
if (node.left != null) {
nextLevel.push(node.left);
}
}
}
result.add(currLevelResult);
tmp = currLevel;
currLevel = nextLevel;
nextLevel = tmp;
normalOrder = !normalOrder;
}
return result;
}
}