Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
74 lines (67 sloc) 1.5 KB
problem:
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]
]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
----------------------------------------------------------------------------------------
solution:
//////////////////
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//两个栈(curLevel, nextLevel)来模拟,并用一个变量记录是l-to-r或r-to-l
vector<vector<int> > zigzagLevelOrder(TreeNode *root)
{
vector<vector<int> > ret;
if(root == NULL)
return ret;
stack<TreeNode*> curLevel, nextLevel;
bool isLToR = true;
curLevel.push(root);
vector<int> tmp;
while(!curLevel.empty())
{
TreeNode *curNode = curLevel.top();
curLevel.pop();
if(curNode)
{
tmp.push_back(curNode->val);
if(isLToR)
{
if(curNode->left)
nextLevel.push(curNode->left);
if(curNode->right)
nextLevel.push(curNode->right);
}
else
{
if(curNode->right)
nextLevel.push(curNode->right);
if(curNode->left)
nextLevel.push(curNode->left);
}
}
if(curLevel.empty())
{
ret.push_back(tmp);
tmp.clear();
isLToR = !isLToR;
swap(curLevel, nextLevel);
}
}
return ret;
}