พิมพ์เส้นทาง K-Sum ทั้งหมดใน Binary Tree ใน C++

ภาพรวมปัญหา

ได้รับ Binary Tree และตัวเลข K ต้องพิมพ์เส้นทางทั้งหมดที่ผลรวมโหนดเท่ากับ K

เส้นทางเริ่ม/จบที่โหนดไหนก็ได้ แต่ต้องไปจากบนลงล่าง (root-to-leaf direction)

ตัวอย่าง

K = 5

Output: 1 3 1, 3 2, 1 4

วิธีแก้ปัญหา

1. ถือแต่ละโหนดว่าเป็นรากชั่วคราว
2. DFS หาเส้นทางจากโหนดนั้นลงไป ผลรวม = K
3. เก็บเส้นทางใน vector ตรวจสอบ suffix sum

ตัวอย่างโค้ด C++

#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;
}

ผลลัพธ์ (Output)

Paths with sum 5 are:
1 3 1
3 2
1 4