ในปัญหานี้ เราได้รับไบนารีทรีและตัวเลข 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
