C++ 中的路径和 III
c++server side programmingprogramming
假设我们给出了一棵二叉树，其中每个节点都包含一个整数键。我们需要找到和等于给定值的路径。路径应该从根节点开始，到叶子节点结束。我们必须找到和相同的路径。
如果树的形式为 [5,4,8,11,null,13,4,7,2,null,null,5,1]，且和为 22，则结果为 −
路径为 [[5,4,11,2],[5,8,4,5]]。
为了解决这个问题，我们将按照以下步骤 −
- 使用 dfs 函数来解决这个问题，dfs 稍加修改，其工作原理如下。此函数将接受根节点、总和和一个临时数组。
- 如果根节点不存在，则返回
- 如果根节点的左侧和右侧为空，则
- 如果总和 = 根节点的值，则
- 将根节点的值插入临时数组，将临时数组插入结果集，并从临时数组中删除最后一个节点
- 返回
- 如果总和 = 根节点的值，则
- 将根节点的值插入临时数组
- dfs(根节点左侧, 总和 - 根节点的值, 临时数组)
- dfs(根节点右侧, 总和 - 根节点的值, 临时数组)
- 从临时数组中删除最后一个元素
让我们看看下面的实现以便更好地理解 −
示例
#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, ],]
