Trong bài toán này, chúng ta được đưa ra một cây nhị phân và một số K và chúng ta phải in ra tất cả các đường dẫn trong cây có tổng các nút trong đường dẫn bằng k.
Ở đây, đường đi của cây có thể bắt đầu từ bất kỳ nút nào của cây và kết thúc ở bất kỳ nút nào. Đường dẫn phải luôn hướng từ nút gốc đến nút lá. Giá trị của các nút của cây có thể là dương, âm hoặc bằng không.
Hãy lấy một ví dụ để hiểu vấn đề -
K =5
Đầu ra -
1 3 1 3 2 1 4
Để giải quyết vấn đề này, chúng ta sẽ coi mỗi nút là nút gốc của cây và tìm đường dẫn từ gốc tạm thời đến các nút khác có tổng giá trị là K.
Chúng tôi lưu trữ tất cả các nút của đường dẫn trong vectơ và kiểm tra giá trị tổng được đánh giá là k.
Ví dụ
Chương trình hiển thị việc triển khai thuật toán -
#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;
} Đầu ra
Paths with sum 5 are − 1 3 1 3 2 1 4