C++ queue BFS version AC in 21ms


  • 0
    S
    void PrintPath(QueueElem *e, vector<int>& v) {
    	QueueElem *c = e;
    	v.clear();
    	while(c && c->node) {
    		v.push_back(c->node->val);
    		c = c->parent;
    	}
    	reverse(v.begin(), v.end());
    }
    bool IsLeaf(TreeNode *n) {
    	return n && !n->left && !n->right;
    }
    //Path Sum II
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
    	vector<vector<int> > result;
    	if(!root)
    		return result;
    
    	queue<QueueElem*> q;
    	vector<QueueElem*> pool;
    	QueueElem *rootElem = new QueueElem(root->val, root, NULL);
    	q.push(rootElem);
    	pool.push_back(rootElem);
    	while(!q.empty()) {
    		QueueElem *cur = q.front();
    		q.pop();
    		if (IsLeaf(cur->node)) {
    			if(cur->sumVal == sum) {
    				vector<int> path;
    				PrintPath(cur, path);
    				result.push_back(path);
    			}				
    		}else{
    			if(cur->node->left) {
    				QueueElem* qleft = new QueueElem(cur->sumVal + cur->node->left->val, cur->node->left, cur);
    				q.push(qleft);
    				pool.push_back(qleft);
    			}
    			if(cur->node->right) {
    				QueueElem* qright = new QueueElem(cur->sumVal + cur->node->right->val, cur->node->right, cur);
    				q.push(qright);
    				pool.push_back(qright);
    			}
    		}
    		//delete cur;
    	}
    
    	for(vector<QueueElem*>::iterator it = pool.begin();
    		it != pool.end(); ++it)
    		delete (*it);
    	return result;
    }

Log in to reply
 

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