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
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] ]
Solution:
在遍历的时候偶数层自左向右，而奇数层自右向左。在Binary Tree Level Order Traversal中我们是维护了一个队列来完成遍历，而在这里为了使每次都倒序出来，我们很容易想到用栈的结构来完成这个操作。有一个区别是这里我们需要一层一层的来处理（原来可以按队列插入就可以，因为后进来的元素不会先处理），所以会同时维护新旧两个栈，一个来读取，一个存储下一层结点。总体来说还是一次遍历完成，所以时间复杂度是O(n)，空间复杂度最坏是两层的结点，所以数量级还是O(n)（满二叉树最后一层的结点是n/2个）。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList> zigzagLevelOrder(TreeNode root) {
ArrayList> res = new ArrayList>();
if(root == null)
return res;
ArrayList list = new ArrayList();
LinkedList stack = new LinkedList();
list.add(root.val);
res.add(list);
stack.push(root);
int level = 1;
while(!stack.isEmpty()) {
list = new ArrayList();
LinkedList newStack = new LinkedList(); //for storing nodes which will be used for next level
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
if(level % 2 == 0) { //偶数层从左向右
if(node.left != null) {
newStack.push(node.left);
list.add(node.left.val);
}
if(node.right != null) {
newStack.push(node.right);
list.add(node.right.val);
}
}else { //奇数层从右向左
if(node.right != null) {
newStack.push(node.right);
list.add(node.right.val);
}
if(node.left != null) {
newStack.push(node.left);
list.add(node.left.val);
}
}
}
level++;
if(list.size() > 0) {
res.add(list);
}
stack = newStack; //assign the newStack to stack, it will be used in next loop
}
return res;
}
}
