数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中的路径和3
假设我们给定了一个二叉树，其中每个节点都有一个整数键。我们必须找到总和为给定值的路径。路径应从根节点开始到叶节点结束。我们必须找到总和相等的路径。
如果树形为[5,4,8,11,null,13,4,7,2,null,null,5,1]，并且总和为22，那么结果将是 -
路径为 [[5,4,11,2],[5,8,4,5]]。
要解决这个问题，我们将按照以下步骤操作 -
- 使用 dfs 函数解决这个问题，dfs 会略作修改，如下所示。此函数将取根、总和和一个临时数组
- 如果根不存在，则返回
- 如果根的左节点和右节点均为空，则
- 如果总和 = 根的值，则
- 将根的值插入 temp，将 temp 插入 result，并将最后一个节点从 temp 中删除
- 返回
- 如果总和 = 根的值，则
- 将根的值插入 temp
- dfs(根的左节点，总和 - 根的值，temp)
- dfs(根的右节点，总和 - 根的值，temp)
- 从 temp 中删除最后一个元素
让我们看以下实现以加深理解 -
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
} else {
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
vector < vector <int> > res;
void dfs(TreeNode* root, int sum, vector <int>& temp){
if(!root)return;
if(!root->left && !root->right){
if(sum == root->val){
temp.push_back(root->val);
res.push_back(temp);
temp.pop_back();
}
return;
}
temp.push_back(root->val);
dfs(root->left, sum - root->val, temp);
dfs(root->right, sum - root->val, temp);
temp.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
res.clear();
vector <int> temp;
dfs(root, sum, temp);
return res;
}
};
main(){
Solution ob;
vector<int> v = {5,4,8,11,NULL,13,4,7,2,NULL,NULL,NULL,NULL,5,1};
TreeNode *root = make_tree(v);
print_vector(ob.pathSum(root, 22));
}输入
[5,4,8,11,null,13,4,7,2,null,null,5,1] 22
输出
[[5, 4, 11, 2, ],[5, 8, 4, 5, ],]
更新于：2020 年 5 月 4 日
201 次浏览
广告