103. Binary Tree Zigzag Level Order Traversal
1. Description
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).
2. Example
Example 1:
Given binary tree [3,9,20,null,null,15,7],
return its zigzag level order traversal as: [[3],[20,9],[15,7]]
3. Solutions
My Accepted Solution
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// vector<vector<int>> zigzagLevelOrder(TreeNode* root)
vector<vector<int>> zigzagLevelOrder(TreeNode *i_root)
{
vector<vector<int>> result;
if(i_root == nullptr) return result;
auto root = i_root;
queue<TreeNode *> currentLayer, nextLayer;
currentLayer.push(root);
bool goRight = true; // control the direction of zigzag, if the direction is from right to left, we reverse the order of nodes at that row
for(vector<int> layer; true; )
{
if(currentLayer.empty())
{
swap(currentLayer, nextLayer);
if(!goRight) reverse(layer.begin(), layer.end());
result.push_back(layer);
layer.clear();
goRight = !goRight;
if(currentLayer.empty()) break;
}
auto currentNode = currentLayer.front();
layer.push_back(currentNode->val);
currentLayer.pop();
if(currentNode->left) nextLayer.push(currentNode->left);
if(currentNode->right) nextLayer.push(currentNode->right);
}
return result;
}
};