## Tuesday, November 11, 2014

### [LeetCode] Binary Tree Zigzag Level Order Traversal

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

Binary Tree Level Order Traversal那题的变种。一样的层序访问，区别仅仅在于访问是左向右，右向左交替进行。
1. 用两个stack来存储curLevel和nextLevel的节点可以实现这样的左右顺序反转。因为stack是先进后出的，节点push进stack的顺序和pop出stack的顺序正好是相反的：

2. 这里还需注意的是push left/right child进nextLevel的顺序。当curLevel从左向右访问时，应当先push(x->left)再push(x->right)，反之则应该先push(x->right)再push(x->left)。实现时可以用一个bool变量left2right来表示顺序，每访问完一层后反转left2right的值。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40``` ```class Solution { public: vector > zigzagLevelOrder(TreeNode *root) { vector> levelNodeValues; if(!root) return levelNodeValues; stack *curLevel = new stack(); stack *nextLevel = new stack(); curLevel->push(root); bool left2right = true; while(!curLevel->empty()) { vector curLevelValues; while(!curLevel->empty()) { TreeNode *cur = curLevel->top(); curLevel->pop(); curLevelValues.push_back(cur->val); if(left2right) { if(cur->left) nextLevel->push(cur->left); if(cur->right) nextLevel->push(cur->right); } else { if(cur->right) nextLevel->push(cur->right); if(cur->left) nextLevel->push(cur->left); } } levelNodeValues.push_back(curLevelValues); // swap curLevel and nextLevel, no need to clear since curLevel is already empty stack *temp = curLevel; curLevel = nextLevel; nextLevel = temp; left2right = !left2right; } return levelNodeValues; } }; ```