?? Binary Trees Series ??
?? Reverse Level Order Traversal
Given a binary tree, perform a reverse level order traversal, i.e., start the traversal from the last level.
Implemented a solution to reverse level order traversal in binary trees. This approach involves using a queue to store nodes during traversal.
Approach:
1) Initialization: Create an empty queue and add the root node to it.
2) Level-by-Level Traversal:
While the queue is not empty:
领英推荐
3) Reverse Order: Print the nodes in the reverse order they were processed.
vector<int> reverseLevelOrder(Node *root)
{
vector<int>ans;
if(root == NULL){
return ans;
}
queue<Node*>q;
q.push(root);
while(!q.empty()){
vector<int>res;
int size = q.size();
for(int i=0 ; i<size ; i++){
Node* frontNode = q.front();
q.pop();
res.push_back(frontNode->data);
if(frontNode->right){
q.push(frontNode->right);
}
if(frontNode->left){
q.push(frontNode->left);
}
}
for(auto i: res){
ans.push_back(i);
}
}
reverse(ans.begin(), ans.end());
return ans;
}
Time Complexity: O(n)
Space Complexity: O(n)