原创内容，转载请注明原文网址：http://homeqin.cn/a/wenzhangboke/jishutiandi/youxikaifa/2018/1224/265.html
在二叉树中找出和为某一值的所有路径
题目：
|
请写一个程序创建一棵二叉树，并按照一定规则，输出二叉树根节点到叶子节点的路径。
规则如下：
1、从最顶端的根结点，到最下面的叶子节点，计算路径通过的所有节点的和，如果与设置的某一值的相同，那么输出这条路径上的所有节点。
2、从根节点遍历树时，请请按照常州网站开发建设左到右遍历，即优先访问左子树的节点。
二叉树创建规则：从上到下一层一层的，按照从左到右的顺序进行构造
输入"10,5,12,4,7"值，构造的树如下：
1） 10
2） 10
/
5
3） 10
/\
5 12
4） 10
/\
5 12
/
4
5） 10
/\
5 12
/\
4 7
针对上面的二叉树，如果当前我们设置的“路径和”为19，那么输出结果为:
10,5,4
如果有多个路径，按到左到右的顺序遍历生成的结果每行显示一个显示。例如如果当前我们设置的“路径和”为22，那么常州游戏开发运营输出结果为:
10,5,7
10,12
如果没有找到路径和为设置的值的路径，输出error。
|
|
运行时间限制: |
无限制 |
|
内存限制: |
无限制 |
|
输入: |
输入整数N---路径和
一行字符串，多个正整数，之间用","隔开
|
|
输出: |
满足条件的二叉树路径
|
|
样例输入: |
22
10,5,12,4,7
|
|
样例输出: |
10,5,7
10,12
|
常州手游开发代码：
#include <iostream>
#include <sstream>
#include <vector>
#include <stdlib.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void creatTree(TreeNode *&root, vector<int>& a, int i, int len)
{
if (i >= len)
return;
root = new TreeNode(a[i]);
creatTree(root->left, a, 2 * i + 1, len);
creatTree(root->right,a, 2 * i + 2, len);
}
void inorderTraversal(TreeNode* root)
{
if (root)
{
cout << root->val << " ";
inorderTraversal(root->left);
inorderTraversal(root->right);
}
}
vector<int> vec;
int sum = 0;
bool isCoutBlank = false;
bool isFind = false;
void pathTree(TreeNode*& root, int target)
{
sum += root->val;
vec.push_back(root->val);
if (sum == target && !root->left && !root->right)
{
isFind = true;
if(isCoutBlank)
cout << endl;
isCoutBlank = true;
for (int i = 0; i < vec.size() - 1; ++i)
{
cout << vec[i]<< ",";
}
cout << vec[vec.size() - 1];
}
if (root->left)
pathTree(root->left, target);
if (root->right)
pathTree(root->right, target);
sum -= root->val;
vec.pop_back();
}
int main()
{
TreeNode* root = nullptr;
int target;
cin >> target;
string val;
cin >> val;
string temp;
stringstream ss(val);
int node;
vector<int> nodes;
while (!ss.eof())
{
getline(ss, temp, ',');
stringstream stmp;
stmp << temp;
stmp >> node;
nodes.push_back(node);
}
creatTree(root, nodes, 0, nodes.size());
pathTree(root,target);
if (!isFind)
cout << "error";
}
常州微信小程序开发
另一种方法：用多个临时vector存储路径值，不用做pop_back操作
#include <iostream>
#include <sstream>
#include <vector>
#include <numeric>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void creatTree(TreeNode *&root, vector<int>& a, int i, int len)
{
if (i >= len)
return;
root = new TreeNode(a[i]);
creatTree(root->left, a, 2 * i + 1, len);
creatTree(root->right,a, 2 * i + 2, len);
}
void inorderTraversal(TreeNode* root)
{
if (root)
{
cout << root->val << " ";
inorderTraversal(root->left);
inorderTraversal(root->right);
}
}
vector<int> vec;
int sum = 0;
bool isCoutBlank = false;
bool isFind = false;
void pathTree(TreeNode*& root, int target)
{
sum += root->val;
vec.push_back(root->val);
if (sum == target && !root->left && !root->right)
{
isFind = true;
if(isCoutBlank)
cout << endl;
isCoutBlank = true;
for (int i = 0; i < vec.size() - 1; ++i)
{
cout << vec[i]<< ",";
}
cout << vec[vec.size() - 1];
}
if (root->left)
pathTree(root->left, target);
if (root->right)
pathTree(root->right, target);
sum -= root->val;
vec.pop_back();
}
void dfs(vector<int> v, TreeNode*& root, int level, int target)
{
if (!root)
return;
v[level++] = root->val;
int sum = accumulate(v.begin(), v.end(),0);
if (!root->left && !root->right && sum == target)
{
isFind = true;
for (int i = 0; i < level; ++i)
{
if (i != 0)
cout << ",";
cout << v[i];
}
cout << endl;
}
if (root->left)
dfs(v, root->left, level, target);
if (root->right)
dfs(v, root->right, level, target);
}
int main()
{
TreeNode* root = nullptr;
int target;
cin >> target;
string val;
cin >> val;
string temp;
stringstream ss(val);
int node;
vector<int> nodes;
while (!ss.eof())
{
getline(ss, temp, ',');
stringstream stmp;
stmp << temp;
stmp >> node;
nodes.push_back(node);
}
creatTree(root, nodes, 0, nodes.size());
// pathTree(root,target);
// if (!isFind)
// cout << "error";
vector<int> vec(nodes.size());
dfs(vec, root, 0, target);
if (!isFind)
cout << "error";
}
上篇：上一篇：
unity3d简单的相机跟随及视野旋转缩放
下篇：下一篇：
常州微信游戏开发-字符串匹配的三种方法
