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]
]
解題思路：
本題是102. Binary Tree Level Order Traversal的變種題疑务，都是層次化遍歷，唯一的區(qū)別是102. Binary Tree Level Order Traversal遍歷的時(shí)候每一層都是從左向右遍歷，而本題遍歷的時(shí)候是奇數(shù)行從左向右而偶數(shù)行從右向左粉臊，因此我們只需要設(shè)置一個(gè)標(biāo)志位篡诽，其他思路基本相同辅愿。
代碼如下：
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;
if(root == NULL) return ret;
TreeNode* curr = root;
queue<TreeNode*> stk;
stk.push(root);
bool leftToRight = true;
while(!stk.empty())
{
int size = stk.size();
vector<int> curLevel(size);
for(int i = 0; i < size; ++i)
{
TreeNode* p = stk.front();
stk.pop();
int index = leftToRight ? i : size - i -1;
curLevel[index] = p->val;
if(p->left) stk.push(p->left);
if(p->right) stk.push(p->right);
}
leftToRight = !leftToRight;
ret.push_back(curLevel);
}
return ret;
}
};
