Using vector instead of Q for BFS


  • -1
    M
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
            vector<vector<int>> res;
            vector<TreeNode*> nodes;
    
        vector<vector<int>> levelOrder(TreeNode* root) {
    
            if(!root)
                return res;
            Addfirstnode(root,res,nodes);
            Addleftrightchild(root,res,nodes);
            
            return res;
            
        }
        void Addfirstnode(TreeNode* root,vector<vector<int>> &res,vector<TreeNode*> &nodes)
        {
            vector<int> res_int;
            //store the root in the res
            res_int.push_back(root->val);
            res.push_back(res_int);
            //store the root in q
            nodes.push_back(root);
            
        }
        void Addleftrightchild(TreeNode* root,vector<vector<int>> &res,vector<TreeNode*> &nodes)
        {
            //exit condition for recurse
        
            if(nodes.size()==0)
                return;
            vector<TreeNode*> nodes_int;vector<int> res_int;
            
            //iterate given nodes list
            for(int i = 0; i < nodes.size(); i++)
            { 
                // add all the left,right child of nodes present in this q  && //add all the corresponding values into res_int
                if(nodes[i]->left)
                {
                    nodes_int.push_back(nodes[i]->left);
                    res_int.push_back(nodes[i]->left->val);
                }
                if(nodes[i]->right)
                {
                    nodes_int.push_back(nodes[i]->right);
                    res_int.push_back(nodes[i]->right->val);
                }
            }
            //now add the row of res_int into res
            if(res_int.size())
                res.push_back(res_int);
            //replace nodes with nodes_int for next iteration
            nodes=nodes_int;
            //recurse
            Addleftrightchild( root, res, nodes);
            
        }
    };

Log in to reply
 

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