Share my BFS 12 ms C++ solution


  • 0
    G
    class Solution {
    public:
    	vector<vector<int>> pathSum(TreeNode* root, int sum) {
    		if (root == NULL) return {};
    		vector<vector<int>> results;
    		queue<TreeNode*> toVisit;
    		toVisit.push(root);
    		queue<vector<int>> tmp;
    		tmp.push({ root->val });
    		while (!toVisit.empty())
    		{
    			int size = toVisit.size();
    
    			for (int i = 0; i < size; i++)
    			{
    				TreeNode* visited = toVisit.front();
    				toVisit.pop();
    				vector<int> cur = tmp.front();
    				tmp.pop();
    
    				if (!visited->left and !visited->right and accumulate(cur.begin(), cur.end(), 0) == sum)
    					results.push_back(cur);
    				if (visited->left)
    				{
    					vector<int> leftVec = cur;
    					leftVec.push_back(visited->left->val);
    					toVisit.push(visited->left);
    					tmp.push(leftVec);
    				}
    
    				if (visited->right)
    				{
    					vector<int> rightVec = cur;
    					rightVec.push_back(visited->right->val);
    					toVisit.push(visited->right);
    					tmp.push(rightVec);
    				}
    			}
    		}
    		return results;
    	}
    };
    

Log in to reply
 

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