C++刷剑指offer（面试题34. 二叉树中和为某一值的路径）【回溯】,C\C++交流,技术交流,鱼C论坛

糖逗发表于 2020-4-4 12:37:57

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

本帖最后由糖逗于 2020-5-8 17:28 编辑

题目描述：
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22，

         5
         / \
         4 8
      / / \
      11134
      /\ / \
   7 25 1
返回:

[
,

]

提示：

节点总数 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
#include <queue>
#include<vector>
using namespace std;

struct TreeNode{
   int val;
   TreeNode* left;
   TreeNode* right;
   TreeNode(int x): val(x), left(NULL), right(NULL){
   }
};

TreeNode* CreateTree(vector<int> input){
   TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
   for(int i = 0; i < input.size(); i++){
            res.val = input;
            res.left = NULL;
            res.right = NULL;
   }
   for(int i= 0; i < input.size(); i++){
            if(2*i+1 < input.size()){
                     res.left = &res;
            }
            if(2*i+2 < input.size()){
                     res.right = &res;
            }

   }
   return res;

}

void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
if(root == NULL) return;
int insert = left + (right - left) / 2;
res = root->val;

middle(root->left, res, left, insert - 1, depth + 1);
middle(root->right, res, insert + 1, right, depth + 1);
}

int treeDepth(TreeNode* root){
if(root == NULL || root -> val == 0) return 0;
return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}

void PrintTree(TreeNode* root) {
int depth = treeDepth(root);
int width = pow(2, depth) - 1;
vector<vector<int> > res(depth, vector<int>(width, 0));
middle(root, res, 0, width - 1, 0);
for(int i = 0; i < res.size(); i++){
            for(int j = 0; j < res.size();j++){
                     if(res == 0){
                           cout<< " ";
                     }
                     else{
                           cout << res;
                     }

            }
            cout << endl;
   }
   cout << "------------------" << endl;
}

void dfs(TreeNode* root, vector<vector<int> >& res, int sum, vector<int>& temp){
temp.push_back(root -> val);
if(sum == root -> val && !root->right && !root -> left){
res.push_back(temp);
}
if(root -> right) dfs(root -> right, res, sum - root->val, temp);
if(root -> left) dfs(root -> left, res, sum - root->val, temp);
temp.pop_back();
}

vector<vector<int> > solution(TreeNode* root, int sum){
vector<vector<int> > res;
vector<int> temp;
if(root == NULL) return res;
dfs(root, res, sum, temp);
return res;
}

int main(void){
   vector<int> input1;
   cout << "send numbers for the first tree" << endl;
   int number1;
   while(cin >> number1){
            input1.push_back(number1);
   }
   cin.clear();
   TreeNode* root = CreateTree(input1);
   PrintTree(root);


   int sum;
   cin >> sum;
   vector<vector<int> > res = solution(root, sum);
   for(int i = 0; i < res.size(); i++){
      for(int j = 0; j < res.size(); j++){
      cout << res << " ";
}
cout << endl;
}

   return 0;
}

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

糖逗发表于 2020-4-4 12:38:40

新增代码：
void dfs(TreeNode* root, vector<vector<int> >& res, int sum, vector<int>& temp){
   temp.push_back(root -> val);
   if(sum == root -> val && !root->right && !root -> left){
            res.push_back(temp);
   }
   if(root -> right) dfs(root -> right, res, sum - root->val, temp);
   if(root -> left) dfs(root -> left, res, sum - root->val, temp);
   temp.pop_back();
}

vector<vector<int> > solution(TreeNode* root, int sum){
   vector<vector<int> > res;
   vector<int> temp;
   if(root == NULL) return res;
   dfs(root, res, sum, temp);
   return res;
}

糖逗发表于 2020-4-7 15:49:20

112. 路径总和
相似题目：
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

         5
         / \
         4 8
      / / \
      11134
      /\    \
   7 2    1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

核心新增代码：
bool solution(TreeNode* root, int target){
if(root == NULL) return false;
if(target == root -> val && root -> right == NULL && root -> left == NULL) return true;
return solution(root -> left, target - root -> val) || solution(root -> right, target - root -> val);

}

int main(void){
cout << "please send the number for the tree" << endl;
vector<int> input;
int number;
while(cin >> number){
input.push_back(number);
}
TreeNode* root = Create
Tree(input);
PrintTree(root);
cin.clear();
int target;
cin >> target;

bool res = solution(root, target);
cout << res << endl;

return 0;
}

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

糖逗发表于 2020-4-8 14:13:19

相似题目：129. 求根到叶子节点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

输入:
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
示例 2:

输入:
4
/ \
9 0
/ \
5 1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
#include <queue>
#include<vector>
using namespace std;

struct TreeNode{
   int val;
   TreeNode* left;
   TreeNode* right;
   TreeNode(int x): val(x), left(NULL), right(NULL){
   }
};

TreeNode* CreateTree(vector<int> input){
TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
for(int i = 0; i < input.size(); i++){
         res.val = input;
         res.left = NULL;
         res.right = NULL;
}
for(int i= 0; i < input.size(); i++){
         if(2*i+1 < input.size()){
               res.left = &res;
         }
         if(2*i+2 < input.size()){
               res.right = &res;
         }

}
return res;

}

void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
if(root == NULL) return;
int insert = left + (right - left) / 2;
res = root->val;

middle(root->left, res, left, insert - 1, depth + 1);
middle(root->right, res, insert + 1, right, depth + 1);
}

int treeDepth(TreeNode* root){
if(root == NULL || root -> val == 0) return 0;
return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}

void PrintTree(TreeNode* root) {
int depth = treeDepth(root);
int width = pow(2, depth) - 1;
vector<vector<int> > res(depth, vector<int>(width, 0));
middle(root, res, 0, width - 1, 0);
for(int i = 0; i < res.size(); i++){
   for(int j = 0; j < res.size();j++){
            if(res == 0){
                     cout<< " ";
            }
            else{
                     cout << res;
            }

   }
   cout << endl;
}
cout << "------------------" << endl;
}

void dfs(TreeNode* root, vector<int>& store, string& temp){
temp += to_string(root -> val);
if(root -> right == NULL && root -> left == NULL) store.push_back(atoi(temp.c_str()));

if(root -> right != NULL)dfs(root -> right, store, temp);
if(root -> left != NULL)dfs(root -> left, store, temp);
temp.erase(temp.size()-1);

}

int solution(TreeNode* root){
if(root == NULL) return 0;
vector<int> store;
string temp;
dfs(root, store, temp);
int res = 0;
for(int i = 0; i< store.size(); i++){
res += store;
}
return res;
}

int main(void){
vector<int> input1;
cout << "send numbers for thetree" << endl;
int number1;
while(cin >> number1){
         input1.push_back(number1);
}
cin.clear();
TreeNode* root = CreateTree(input1);
PrintTree(root);

int res = solution(root);
cout << res << endl;
return 0;
}

页: [1]

鱼C论坛's Archiver

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