C++ Efficient Solution


#1
vector<vector<int> > Solution::levelOrder(TreeNode* A) {
    queue<TreeNode*>s,p;
    vector<vector<int>> a;
    vector<int> temp;
    TreeNode* t=A;
    s.push(t);
    int k=0;
    temp.push_back(t->val);
    a.push_back(temp);
    temp.clear();
    //cout<<a[0][0];
    while(!s.empty() || !p.empty())
    {   if(s.empty())
        {
            while(!p.empty())
            {
                s.push(p.front());
                p.pop();
            }
        a.push_back(temp);
        temp.clear();
        }
        t=s.front();
        s.pop();
            if(t->left)
            {
                p.push(t->left);
                temp.push_back(t->left->val);
            }
            if(t->right)
            {
                p.push(t->right);
                temp.push_back(t->right->val);
            }
        
    }
    return a;
}

#2

I think the idea behind your solution is maintaining 2 queues for alternate levels
correct me if I am wrong!
this is my take according to this logic

vector<vector<int> > Solution::levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    // bfs(root);
    queue<TreeNode*> qu1;
    queue<TreeNode*> qu2;
    qu1.push(root);
    TreeNode* temp=root;
    while(!qu1.empty()||!qu2.empty())
    {
        if(qu2.empty())
        {
            ans.push_back(vector<int>());
            //q1 has something
            while(!qu1.empty())
            {
                TreeNode* temp=qu1.front();
                qu1.pop();
                ans[ans.size()-1].push_back(temp->val);
                if(temp->left!=NULL)
                {
                    qu2.push(temp->left);
                }
                if(temp->right!=NULL)
                {
                    qu2.push(temp->right);
                }
                
            }
        }
        else{
            ans.push_back(vector<int>());
            //q1 has something
            while(!qu2.empty())
            {
                TreeNode* temp=qu2.front();
                qu2.pop();
                ans[ans.size()-1].push_back(temp->val);
                if(temp->left!=NULL)
                {
                    qu1.push(temp->left);
                }
                if(temp->right!=NULL)
                {
                    qu1.push(temp->right);
                }
                
            }
        }
    }
    return ans;
    
}

#3

I don’t see reasons why needing to have two queues, I only had one queue<pair<TreeNode, int>>, where first is the current node and second is current level so far (i use this to create new levels in my return vector.
Code:

vector<vector<int> > Solution::levelOrder(TreeNode* A) {
    queue<pair<TreeNode, int> > bfs;
    vector<vector<int> > depthTree;
    bfs.push(make_pair(*(A), 0));
    int currNodeLevel = -1;
    while (!bfs.empty()) {
        TreeNode currNode = bfs.front().first;
        int currLevel = bfs.front().second;
        bfs.pop();
        if (currNodeLevel < currLevel) {
            depthTree.push_back(vector<int>(0));
            currNodeLevel = currLevel;
        }
        depthTree[currLevel].push_back(currNode.val);
        if (currNode.left != NULL) {
            bfs.push(make_pair(*(currNode.left), currLevel + 1));
        }
        if (currNode.right != NULL) {
            bfs.push(make_pair(*(currNode.right), currLevel + 1));
        }
    }
    
    return depthTree;
    
}