Very simple BFS traversal


#1
vector<vector<int> > Solution::levelOrder(TreeNode* A) {
    vector<vector<int>> ans;
    ans.push_back(vector<int>());
    
    //queue for traversing the tree using BFS
    queue<TreeNode*> q;
    
    //add the first level, and also add the EOLevel marker
    q.push(A);
    q.push(NULL);
    
    //do BFS
    while(!q.empty()){
        TreeNode* n = q.front(); q.pop();
        if(!n){
            //NULL found, end of level. Create a new level if it exists
            if(!q.empty()) {
                q.push(NULL);
                ans.push_back(vector<int>());
            }
        }else{
            //add this value to the latest level
            ans[ans.size()-1].push_back(n->val);
            if(n->left) q.push(n->left);
            if(n->right) q.push(n->right);
        }
    }
    return ans;
}