113. Path Sum II

欢迎fork and star：Nowcoder-Repository-github

113. Path Sum II

题目

1 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
2For example:
3Given the below binary tree and sum = 22,
4
5              5
6             / \
7            4   8
8           /   / \
9          11  13  4
10         /  \    / \
11        7    2  5   1
12
13return
14
15[
16   [5,4,11,2],
17   [5,8,4,5]
18]
19

解析

• 采用dfs和bfs的方法，很经典的方法，类似的题目很多都可以采用此方法，熟练掌握！

  class Solution_113 { public:

  1void dfs(TreeNode* root,int cur_sum,int sum,vector<int> &vec ,vector<vector<int>> &vecs)
  2{
  3	if (!root)
  4	{
  5		return;
  6	}
  7
  8	if (root->left==NULL&&root->right==NULL&&cur_sum==sum)
  9	{
  10		vecs.push_back(vec);
  11		return;
  12	}
  13	if (root->left)
  14	{
  15		vec.push_back(root->left->val);
  16		dfs(root->left, cur_sum + root->left->val, sum, vec, vecs);
  17		vec.pop_back();
  18	}
  19	if (root->right)
  20	{
  21		vec.push_back(root->right->val);
  22		dfs(root->right, cur_sum + root->right->val, sum, vec, vecs);
  23		vec.pop_back();
  24	}
  25	
  26	return;
  27}
  28
  29vector<vector<int> > pathSum1(TreeNode *root, int sum) {
  30	vector<vector<int>> vecs;
  31	vector<int> vec;
  32
  33	if (!root)
  34	{
  35		return vecs;
  36	}
  37
  38	vec.push_back(root->val);
  39	dfs(root,root->val,sum,vec,vecs); //输入当前节点及其当前节点的和
  40	return vecs;
  41}
  42
  43vector<vector<int> > pathSum(TreeNode *root, int sum) {
  44
  45	vector<vector<int>> vecs;
  46
  47	if (!root)
  48	{
  49		return vecs;
  50	}
  51
  52	queue<TreeNode*> que;
  53	que.push(root);
  54
  55	queue<vector<int>> path;
  56	path.push({ root->val }); 
  57
  58	while (!que.empty())
  59	{
  60		TreeNode* temp;
  61		int size = que.size();
  62
  63		for (int i = 0; i < size;i++)
  64		{
  65			temp = que.front();
  66			que.pop();
  67
  68			vector<int>  vec= path.front();
  69			path.pop();
  70
  71			if (temp->left==NULL&&temp->right==NULL&& accumulate(vec.begin(),vec.end(),0)==sum) //0 累加的初始值
  72			{
  73				vecs.push_back(vec);
  74			}
  75			if (temp->left)
  76			{
  77				que.push(temp->left);
  78
  79				vector<int> var = vec;
  80				var.push_back(temp->left->val);
  81				path.push(var);
  82				//vec.pop_back();
  83			}
  84			if (temp->right)
  85			{
  86				que.push(temp->right);
  87				vector<int> var = vec;
  88				var.push_back(temp->right->val);
  89				path.push(var);
  90				//vec.pop_back();
  91			}
  92		}
  93	}
  94	return vecs;
  95}
  

  };

题目来源

• 113. Path Sum II