数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究在 C++ 中打印二叉树中的所有 k 和路径
本题给出一个二叉树和一个数字 K，我们需要打印出树中的所有路径，这些路径中节点的和等于 k。
这里，树的路径可以从树的任何节点开始，在任何节点结束。路径应该总是从根节点直达叶节点。树中节点的值可以为正、负或零。
来看一个例子来理解本题 −
K = 5
输出 −
1 3 1 3 2 1 4
要解决本题，我们将每个节点视为树的根节点，并从临时根节点到其他节点找出路径和为 K。
我们将路径中的所有节点存储在向量中，并检查和值是否为 k。
示例
演示算法实现的程序 −
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left,*right;
Node(int x){
data = x;
left = right = NULL;
}
};
void printPath(const vector<int>& v, int i) {
for (int j=i; j<v.size(); j++)
cout<<v[j]<<"\t";
cout<<"\n";
}
void findKSumPath(Node *root, vector<int>& path, int k) {
if (!root)
return;
path.push_back(root->data);
findKSumPath(root->left, path, k);
findKSumPath(root->right, path, k);
int f = 0;
for (int j=path.size()-1; j>=0; j--){
f += path[j];
if (f == k)
printPath(path, j);
}
path.pop_back();
}
int main() {
Node *root = new Node(1);
root->left = new Node(3);
root->left->left = new Node(1);
root->left->right = new Node(2);
root->right = new Node(4);
root->right->right = new Node(7);
int k = 5;
cout<<"Paths with sum "<<k<<" are :\n";
vector<int> path;
findKSumPath(root, path, k);
return 0;
}输出
Paths with sum 5 are − 1 3 1 3 2 1 4
更新时间： 2020 年 1 月 22 日
426 次浏览
广告