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] ]
confused what "{1,#,2,3}" means > read more on how binary tree is serialized on OJ.
我使用了两个deque容器做，其实可以使用stack。
代码还是非常清晰的，一块一块的分好，思路很容易跟的。
class Solution {
public:
vector
> zigzagLevelOrder(TreeNode *root)
{
vector
> v; if (!root) return v; deque
qt1; deque
qt2; qt1.push_back(root); vector
itmedia; itmedia.push_back(root->val); v.push_back(itmedia); itmedia.clear(); while (!qt1.empty()) { while (!qt1.empty()) { TreeNode *t = qt1.back(); qt1.pop_back(); if (t->right) { qt2.push_back(t->right); itmedia.push_back(t->right->val); } if (t->left) { qt2.push_back(t->left); itmedia.push_back(t->left->val); } } if (!itmedia.empty()) v.push_back(itmedia); itmedia.clear(); while (!qt2.empty()) { TreeNode *t = qt2.back(); qt2.pop_back(); if (t->left) { qt1.push_back(t->left); itmedia.push_back(t->left->val); } if (t->right) { qt1.push_back(t->right); itmedia.push_back(t->right->val); } } if (!itmedia.empty()) v.push_back(itmedia); itmedia.clear(); } return v; } };