Skip to content

Instantly share code, notes, and snippets.

@cpragadeesh
Created November 12, 2018 07:19
Show Gist options
  • Save cpragadeesh/5c5ee72fbe70a47cd2061f7df62cd469 to your computer and use it in GitHub Desktop.
Save cpragadeesh/5c5ee72fbe70a47cd2061f7df62cd469 to your computer and use it in GitHub Desktop.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
queue <TreeNode*> q;
if(root == NULL)
return {};
if(root->left == NULL && root->right == NULL)
return {{root->val}};
int level = 0;
q.push(root);
while(!q.empty()) {
int size = q.size();
result.push_back(vector<int>());
for(int i = 0; i < size; ++i) {
TreeNode *node = q.front();
q.pop();
result[level].push_back(node->val);
if(node->left != NULL)
q.push(node->left);
if(node->right != NULL)
q.push(node->right);
}
++level;
}
for(int i = 0; i < result.size(); ++i) {
if(i % 2 == 1) {
reverse(result[i].begin(), result[i].end());
}
}
return result;
}
};
@cpragadeesh
Copy link
Author

line 20: unnecessary exit? you can do that in while loop
line 29: you know the size of the vector. You should use the constructor where you can specify the size for optimisation.
line 44: level is not used anywhere
line 50: Can you do it without using this extra for loop and reverse statements? Takes additional O(n) for no reason.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment