Level Order Traversal using Queue


  • 0
    S

    The idea is to do a level order traversal and saving it to a vector followed by reversal of elements in the vector

    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            queue<TreeNode*> q;
            queue<int> qLevel;
            vector<vector<int>> v;
            if(root==NULL){
                return v;
            }
            q.push(root);
            qLevel.push(0);
            while(!q.empty()){
                TreeNode *temp = new TreeNode(0);
                temp=q.front();
                q.pop();
                int level=qLevel.front();
                qLevel.pop();
                if(level>=v.size()){
                    vector<int> vTemp;
                    vTemp.push_back(temp->val);
                    v.push_back(vTemp);
                }else{
                    v[level].push_back(temp->val);
                }
                if(temp->left!=NULL){
                    q.push(temp->left);
                    qLevel.push(level+1);
                }
                if(temp->right!=NULL){
                    q.push(temp->right);
                    qLevel.push(level+1);
                }
            }
            for(int i=0;i<v.size()/2;i++){
                swap(v[i],v[v.size()-1-i]);
            }
            return v;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.