Prose instead of Poetry: My BFS with C++


  • 0
    B

    In BFS, track if you are one even level or odd level from root and create a vector each time you move between the levels Finally reverse the results by popping from stack. May be not minimal number of lines but I like verbose if the complexity of solution is going to be same as a more concise solution.

    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int> > result;
            if (!root) return result;
            stack<vector<int> > res;
            queue<TreeNode*> bfs_odd, bfs_even;
            bfs_even.push(root); 
            while (!bfs_even.empty() || !bfs_odd.empty())
            {
                std::vector<int> level;
                while(!bfs_even.empty())
                {
                TreeNode* temp = bfs_even.front(); bfs_even.pop();
                level.push_back(temp->val);
                if (temp->left!=NULL)  {bfs_odd.push(temp->left); }
                if (temp->right!=NULL) {bfs_odd.push(temp->right);}
                }
                if (!level.empty()) res.push(level);
                
                level.clear();
                while(!bfs_odd.empty())
                {
                TreeNode* temp = bfs_odd.front(); bfs_odd.pop();
                level.push_back(temp->val);
                if (temp->left!=NULL)  {bfs_even.push(temp->left);}
                if (temp->right!=NULL) {bfs_even.push(temp->right);}
                }  
                if (!level.empty()) res.push(level);            
            }
    
            while (!res.empty())
              {
                  vector<int> x = res.top(); res.pop();
                  result.push_back(x);
              }
            return result;
            
        }
    };

Log in to reply
 

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