Bfs and dfs with c++


  • 1
    Y
    vector<vector<int>> result;
    vector<vector<int>> pathSum(TreeNode* root, int sum){
    	if (!root) return result;
    	//vector<int>tmp;
    	//dfs(root,sum,0,tmp);
    	bfs(root,sum);
    	return result;
    }
    void bfs(TreeNode* root, int target)
    {
    	//使用宽度优先遍历,需要加一个队列记录当前节点的和
    	//bfs
    
    	TreeNode*current = NULL;
    	queue<TreeNode*>myQueue;
    	queue<int>sum;
    	myQueue.push(root);
    	sum.push(root->val);
    
    	map<TreeNode*, TreeNode*> prePath;  //store the prefix for rebuilding the path
    	vector<TreeNode*> res;  //store the "right" nodes  
    	int currentSum;
    	while (!myQueue.empty())
    	{
    		current = myQueue.front();
    		currentSum = sum.front();
    
    		if (currentSum == target&&!current->left&&!current->right) res.push_back(current);
    		myQueue.pop();
    		sum.pop();
    		if (current->left != NULL)
    		{
    			myQueue.push(current->left);
    			sum.push(currentSum + current->left->val);
    			prePath[current->left] = current;
    		}
    		if (current->right != NULL)
    		{
    			myQueue.push(current->right);
    			sum.push(currentSum + current->right->val);
    			prePath[current->right] = current;
    		}
    	}
    	// rebuild the path
    	vector<int>tmp;
    	for (int i = 0; i < res.size(); i++)
    	{
    		current = res[i];
    		tmp.clear();
    		while (current!=root)
    		{
    			tmp.push_back(current->val);
    			current = prePath[current];
    		}
    		tmp.push_back(root->val);
    		reverse(tmp.begin(),tmp.end());
    		result.push_back(tmp);
    	}
    }
    void dfs(TreeNode* root, int target, int current,vector<int>res)
    {
    	//深度优先很简洁
    	//very neat
    	res.push_back(root->val);
    	if (!root->left &&!root->right)
    		if (current + root->val == target) result.push_back(res);
    		else res.pop_back();
    	else
    	{
    		if (root->left) dfs(root->left, target, current + root->val, res);
    		if (root->right) dfs(root->right, target, current + root->val, res);
    		res.pop_back();
    	}
    
    }

Log in to reply
 

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