在二叉树中找出和为某一值的所有路径

题目：

请写一个程序创建一棵二叉树，并按照一定规则，输出二叉树根节点到叶子节点的路径。

规则如下：
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

代码：

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 #include <stdlib.h>
 5 
 6 using namespace std;
 7 
 8 struct TreeNode
 9 {
10     int val;
11     TreeNode *left, *right;
12     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13 };
14 
15 void creatTree(TreeNode *&root, vector<int>& a, int i, int len)
16 {
17     if (i >= len)
18         return;
19     root = new TreeNode(a[i]);
20     creatTree(root->left, a, 2 * i + 1, len);
21     creatTree(root->right,a, 2 * i + 2, len);
22 }
23 
24 void inorderTraversal(TreeNode* root)
25 {
26     if (root)
27     {
28         cout << root->val << " ";
29         inorderTraversal(root->left);
30         inorderTraversal(root->right);
31     }
32 }
33 
34 vector<int> vec;
35 int sum = 0;
36 bool isCoutBlank = false;
37 bool isFind = false;
38 void pathTree(TreeNode*& root, int target)
39 {
40     sum += root->val;
41     vec.push_back(root->val);
42     if (sum == target && !root->left && !root->right)
43     {
44         isFind = true;
45         if(isCoutBlank)
46             cout << endl;
47         isCoutBlank = true;
48         for (int i = 0; i < vec.size() - 1; ++i)
49         {
50             cout << vec[i]<< ",";
51         }
52         cout << vec[vec.size() - 1];
53     }
54     if (root->left)
55         pathTree(root->left, target);
56     if (root->right)
57         pathTree(root->right, target);
58     sum -= root->val;
59     vec.pop_back();
60 }
61 
62 
63 int main()
64 {
65     TreeNode* root = nullptr;
66     int target;
67     cin >> target;
68     string val;
69     cin >> val;
70     string temp;
71     stringstream ss(val);
72     int node;
73     vector<int> nodes;
74     while (!ss.eof())
75     {
76         getline(ss, temp, ',');
77         stringstream stmp;
78         stmp << temp;
79         stmp >> node;
80         nodes.push_back(node);
81     }
82     creatTree(root, nodes, 0, nodes.size());
83     pathTree(root,target);
84     if (!isFind)
85         cout << "error";
86 }

另一种方法：用多个临时vector存储路径值，不用做pop_back操作

  1 #include <iostream>
  2 #include <sstream>
  3 #include <vector>
  4 #include <numeric>
  5 
  6 using namespace std;
  7 
  8 struct TreeNode
  9 {
 10     int val;
 11     TreeNode *left, *right;
 12     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 13 };
 14 
 15 void creatTree(TreeNode *&root, vector<int>& a, int i, int len)
 16 {
 17     if (i >= len)
 18         return;
 19     root = new TreeNode(a[i]);
 20     creatTree(root->left, a, 2 * i + 1, len);
 21     creatTree(root->right,a, 2 * i + 2, len);
 22 }
 23 
 24 void inorderTraversal(TreeNode* root)
 25 {
 26     if (root)
 27     {
 28         cout << root->val << " ";
 29         inorderTraversal(root->left);
 30         inorderTraversal(root->right);
 31     }
 32 }
 33 
 34 vector<int> vec;
 35 int sum = 0;
 36 bool isCoutBlank = false;
 37 bool isFind = false;
 38 void pathTree(TreeNode*& root, int target)
 39 {
 40     sum += root->val;
 41     vec.push_back(root->val);
 42     if (sum == target && !root->left && !root->right)
 43     {
 44         isFind = true;
 45         if(isCoutBlank)
 46             cout << endl;
 47         isCoutBlank = true;
 48         for (int i = 0; i < vec.size() - 1; ++i)
 49         {
 50             cout << vec[i]<< ",";
 51         }
 52         cout << vec[vec.size() - 1];
 53     }
 54     if (root->left)
 55         pathTree(root->left, target);
 56     if (root->right)
 57         pathTree(root->right, target);
 58     sum -= root->val;
 59     vec.pop_back();
 60 }
 61 
 62 void dfs(vector<int> v, TreeNode*& root, int level, int target)
 63 {
 64     if (!root)
 65         return;
 66     v[level++] = root->val;
 67     int sum = accumulate(v.begin(), v.end(),0);
 68     if (!root->left && !root->right && sum == target)
 69     {
 70         isFind = true;
 71         for (int i = 0; i < level; ++i)
 72         {
 73             if (i != 0)
 74                 cout << ",";
 75             cout << v[i];
 76         }
 77         cout << endl;
 78     }
 79     if (root->left)
 80         dfs(v, root->left, level, target);
 81     if (root->right)
 82         dfs(v, root->right, level, target);
 83 }
 84 
 85 int main()
 86 {
 87     TreeNode* root = nullptr;
 88     int target;
 89     cin >> target;
 90     string val;
 91     cin >> val;
 92     string temp;
 93     stringstream ss(val);
 94     int node;
 95     vector<int> nodes;
 96     while (!ss.eof())
 97     {
 98         getline(ss, temp, ',');
 99         stringstream stmp;
100         stmp << temp;
101         stmp >> node;
102         nodes.push_back(node);
103     }
104     creatTree(root, nodes, 0, nodes.size());
105 //     pathTree(root,target);
106 //     if (!isFind)
107 //         cout << "error";
108     vector<int> vec(nodes.size());
109     dfs(vec, root, 0, target);
110     if (!isFind)
111         cout << "error";
112 }