C++刷剑指offer（面试题34. 二叉树中和为某一值的路径）【回溯】

糖逗

题目描述：

1. 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
   
2. 
   
3.  
   
4. 
   
5. 示例:
   
6. 给定如下二叉树，以及目标和 sum = 22，
   
7. 
   
8.               5
   
9.              / \
   
10.             4   8
    
11.            /   / \
    
12.           11  13  4
    
13.          /  \    / \
    
14.         7    2  5   1
    
15. 返回:
    
16. 
    
17. [
    
18.    [5,4,11,2],
    
19.    [5,8,4,5]
    
20. ]
    
21.  
    
22. 
    
23. 提示：
    
24. 
    
25. 节点总数 <= 10000
    
26. 
    
27. 来源：力扣（LeetCode）
    
28. 链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
    
29. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<iostream>
   
2. #include <malloc.h>
   
3. #include <vector>
   
4. #include <math.h>
   
5. #include <queue>
   
6. #include<vector>
   
7. using namespace std;
   
8. 
   
9. struct TreeNode{
   
10.         int val;
    
11.         TreeNode* left;
    
12.         TreeNode* right;
    
13.         TreeNode(int x): val(x), left(NULL), right(NULL){
    
14.         }
    
15. };
    
16. 
    
17. TreeNode* CreateTree(vector<int> input){
    
18.         TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
19.         for(int i = 0; i < input.size(); i++){
    
20.                 res[i].val = input[i];
    
21.                 res[i].left = NULL;
    
22.                 res[i].right = NULL;
    
23.         }
    
24.         for(int i= 0; i < input.size(); i++){
    
25.                 if(2*i+1 < input.size()){
    
26.                         res[i].left = &res[2*i+1];
    
27.                 }
    
28.                 if(2*i+2 < input.size()){
    
29.                         res[i].right = &res[2*i+2];
    
30.                 }
    
31.                
    
32.         }
    
33.         return res;
    
34.         
    
35. }
    
36. 
    
37. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
38.     if(root == NULL) return;
    
39.     int insert = left + (right - left) / 2;
    
40.     res[depth][insert] = root->val;
    
41.            
    
42.     middle(root->left, res, left, insert - 1, depth + 1);
    
43.     middle(root->right, res, insert + 1, right, depth + 1);
    
44.     }
    
45. 
    
46. int treeDepth(TreeNode* root){
    
47.     if(root == NULL || root -> val == 0) return 0;
    
48.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    
49. }
    
50.       
    
51. void PrintTree(TreeNode* root) {
    
52.     int depth = treeDepth(root);
    
53.     int width = pow(2, depth) - 1;
    
54.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
55.     middle(root, res, 0, width - 1, 0);
    
56.     for(int i = 0; i < res.size(); i++){
    
57.                 for(int j = 0; j < res[i].size();j++){
    
58.                         if(res[i][j] == 0){
    
59.                                 cout  << " ";
    
60.                         }
    
61.                         else{
    
62.                                 cout << res[i][j];
    
63.                         }
    
64.                        
    
65.                 }
    
66.                 cout << endl;
    
67.         }
    
68.         cout << "------------------" << endl;
    
69.     }
    
70. 
    
71. 
    
72. 
    
73. void dfs(TreeNode* root, vector<vector<int> >& res, int sum, vector<int>& temp){
    
74.         temp.push_back(root -> val);
    
75.         if(sum == root -> val && !root->right && !root -> left){
    
76.                 res.push_back(temp);
    
77.         }
    
78.         if(root -> right) dfs(root -> right, res, sum - root->val, temp);
    
79.         if(root -> left) dfs(root -> left, res, sum - root->val, temp);
    
80.         temp.pop_back();
    
81. }
    
82. 
    
83. 
    
84. vector<vector<int> > solution(TreeNode* root, int sum){
    
85.         vector<vector<int> > res;
    
86.         vector<int> temp;
    
87.         if(root == NULL) return res;
    
88.         dfs(root, res, sum, temp);
    
89.         return res;
    
90. }
    
91. 
    
92. 
    
93. 
    
94. int main(void){
    
95.         vector<int> input1;
    
96.         cout << "send numbers for the first tree" << endl;
    
97.         int number1;
    
98.         while(cin >> number1){
    
99.                 input1.push_back(number1);
    
100.         }
     
101.         cin.clear();
     
102.         TreeNode* root = CreateTree(input1);
     
103.         PrintTree(root);
     
104.         
     
105.         
     
106.         int sum;
     
107.         cin >> sum;
     
108.         vector<vector<int> > res = solution(root, sum);
     
109.         for(int i = 0; i < res.size(); i++){
     
110.                 for(int j = 0; j < res[0].size(); j++){
     
111.                         cout << res[i][j] << " ";
     
112.                         }
     
113.                         cout << endl;
     
114.                 }
     
115.         
     
116.         return 0;
     
117. }
     

复制代码

注意事项：
1.回溯法
2.本地调试后未输出多个方案，但leetcode上通过了。

糖逗

新增代码：

1. void dfs(TreeNode* root, vector<vector<int> >& res, int sum, vector<int>& temp){
   
2.         temp.push_back(root -> val);
   
3.         if(sum == root -> val && !root->right && !root -> left){
   
4.                 res.push_back(temp);
   
5.         }
   
6.         if(root -> right) dfs(root -> right, res, sum - root->val, temp);
   
7.         if(root -> left) dfs(root -> left, res, sum - root->val, temp);
   
8.         temp.pop_back();
   
9. }
   
10. 
    
11. 
    
12. vector<vector<int> > solution(TreeNode* root, int sum){
    
13.         vector<vector<int> > res;
    
14.         vector<int> temp;
    
15.         if(root == NULL) return res;
    
16.         dfs(root, res, sum, temp);
    
17.         return res;
    
18. }

复制代码

糖逗

112. 路径总和
相似题目：

1. 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
   
2. 
   
3. 说明:&#160;叶子节点是指没有子节点的节点。
   
4. 
   
5. 示例:&#160;
   
6. 给定如下二叉树，以及目标和 sum = 22，
   
7. 
   
8.               5
   
9.              / \
   
10.             4   8
    
11.            /   / \
    
12.           11  13  4
    
13.          /  \      \
    
14.         7    2      1
    
15. 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
    
16. 
    
17. 来源：力扣（LeetCode）
    
18. 链接：https://leetcode-cn.com/problems/path-sum
    
19. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

核心新增代码：

1. bool solution(TreeNode* root, int target){
   
2.         if(root == NULL) return false;
   
3.         if(target == root -> val && root -> right == NULL && root -> left == NULL) return true;
   
4.         return solution(root -> left, target - root -> val) || solution(root -> right, target - root -> val);
   
5. 
   
6. }
   
7. 
   
8. int main(void){
   
9.         cout << "please send the number for the tree" << endl;
   
10.         vector<int> input;
    
11.         int number;
    
12.         while(cin >> number){
    
13.                 input.push_back(number);
    
14.         }
    
15.         TreeNode* root = Create
    
16.         Tree(input);
    
17.         PrintTree(root);
    
18.         cin.clear();
    
19.         int target;
    
20.         cin >> target;
    
21.        
    
22.         bool res = solution(root, target);
    
23.         cout << res << endl;
    
24.        
    
25.         return 0;
    
26. }

复制代码

注意要点：
1.使用了深度优先搜索。

糖逗

相似题目：129. 求根到叶子节点数字之和

1. 给定一个二叉树，它的每个结点都存放一个&#160;0-9&#160;的数字，每条从根到叶子节点的路径都代表一个数字。
   
2. 
   
3. 例如，从根到叶子节点路径 1->2->3 代表数字 123。
   
4. 
   
5. 计算从根到叶子节点生成的所有数字之和。
   
6. 
   
7. 说明:&#160;叶子节点是指没有子节点的节点。
   
8. 
   
9. 示例 1:
   
10. 
    
11. 输入: [1,2,3]
    
12.     1
    
13.    / \
    
14.   2   3
    
15. 输出: 25
    
16. 解释:
    
17. 从根到叶子节点路径 1->2 代表数字 12.
    
18. 从根到叶子节点路径 1->3 代表数字 13.
    
19. 因此，数字总和 = 12 + 13 = 25.
    
20. 示例 2:
    
21. 
    
22. 输入: [4,9,0,5,1]
    
23.     4
    
24.    / \
    
25.   9   0
    
26. &#160;/ \
    
27. 5   1
    
28. 输出: 1026
    
29. 解释:
    
30. 从根到叶子节点路径 4->9->5 代表数字 495.
    
31. 从根到叶子节点路径 4->9->1 代表数字 491.
    
32. 从根到叶子节点路径 4->0 代表数字 40.
    
33. 因此，数字总和 = 495 + 491 + 40 = 1026.
    
34. 
    
35. 来源：力扣（LeetCode）
    
36. 链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
    
37. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<iostream>
   
2. #include <malloc.h>
   
3. #include <vector>
   
4. #include <math.h>
   
5. #include <queue>
   
6. #include<vector>
   
7. using namespace std;
   
8. 
   
9. struct TreeNode{
   
10.         int val;
    
11.         TreeNode* left;
    
12.         TreeNode* right;
    
13.         TreeNode(int x): val(x), left(NULL), right(NULL){
    
14.         }
    
15. };
    
16. 
    
17. TreeNode* CreateTree(vector<int> input){
    
18.     TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
19.     for(int i = 0; i < input.size(); i++){
    
20.             res[i].val = input[i];
    
21.             res[i].left = NULL;
    
22.             res[i].right = NULL;
    
23.     }
    
24.     for(int i= 0; i < input.size(); i++){
    
25.             if(2*i+1 < input.size()){
    
26.                     res[i].left = &res[2*i+1];
    
27.             }
    
28.             if(2*i+2 < input.size()){
    
29.                     res[i].right = &res[2*i+2];
    
30.             }
    
31.            
    
32.     }
    
33.     return res;
    
34.         
    
35. }
    
36. 
    
37. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
38.     if(root == NULL) return;
    
39.     int insert = left + (right - left) / 2;
    
40.     res[depth][insert] = root->val;
    
41.            
    
42.     middle(root->left, res, left, insert - 1, depth + 1);
    
43.     middle(root->right, res, insert + 1, right, depth + 1);
    
44.     }
    
45. 
    
46. int treeDepth(TreeNode* root){
    
47.     if(root == NULL || root -> val == 0) return 0;
    
48.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    
49. }
    
50.       
    
51. void PrintTree(TreeNode* root) {
    
52.     int depth = treeDepth(root);
    
53.     int width = pow(2, depth) - 1;
    
54.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
55.     middle(root, res, 0, width - 1, 0);
    
56.     for(int i = 0; i < res.size(); i++){
    
57.         for(int j = 0; j < res[i].size();j++){
    
58.                 if(res[i][j] == 0){
    
59.                         cout  << " ";
    
60.                 }
    
61.                 else{
    
62.                         cout << res[i][j];
    
63.                 }
    
64.                
    
65.         }
    
66.         cout << endl;
    
67.     }
    
68.     cout << "------------------" << endl;
    
69. }
    
70. 
    
71. void dfs(TreeNode* root, vector<int>& store, string& temp){
    
72.     temp += to_string(root -> val);
    
73.         if(root -> right == NULL && root -> left == NULL) store.push_back(atoi(temp.c_str()));
    
74.        
    
75.         if(root -> right != NULL)dfs(root -> right, store, temp);
    
76.         if(root -> left != NULL)dfs(root -> left, store, temp);
    
77.         temp.erase(temp.size()-1);
    
78. 
    
79. }
    
80. 
    
81. 
    
82. int solution(TreeNode* root){
    
83.         if(root == NULL) return 0;
    
84.     vector<int> store;
    
85.     string temp;
    
86.         dfs(root, store, temp);
    
87.         int res = 0;
    
88.         for(int i = 0; i< store.size(); i++){
    
89.                 res += store[i];
    
90.         }
    
91.         return res;
    
92. }
    
93. 
    
94. int main(void){
    
95.         vector<int> input1;
    
96.     cout << "send numbers for the  tree" << endl;
    
97.     int number1;
    
98.     while(cin >> number1){
    
99.             input1.push_back(number1);
    
100.     }
     
101.     cin.clear();
     
102.     TreeNode* root = CreateTree(input1);
     
103.     PrintTree(root);
     
104.    
     
105.    
     
106.     int res = solution(root);
     
107.     cout << res << endl;
     
108.     return 0;
     
109. }
     
110. 
     

复制代码