In Tất Cả Đường Đi Tổng K Trong Cây Nhị Phân Trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân và một số K. In tất cả đường đi trong cây có tổng giá trị các nút bằng K.

Đường đi có thể bắt đầu từ bất kỳ nút nào và kết thúc tại bất kỳ nút nào. Đường đi luôn đi từ gốc xuống lá. Giá trị nút có thể dương, âm hoặc 0.

Ví dụ để hiểu vấn đề:

K = 5

Đầu ra:

1 3 1
3 2
1 4

Để giải quyết, ta coi mỗi nút như gốc tạm thời và tìm đường đi từ gốc tạm đến các nút khác có tổng bằng K.

Lưu các nút trên đường đi vào vector và kiểm tra tổng bằng K.

Ví Dụ

Chương trình minh họa 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 << "Các đường đi có tổng " << k << " là:\n";
    vector<int> path;
    findKSumPath(root, path, k);
    return 0;
}

Đầu Ra

Các đường đi có tổng 5 là:
1 3 1
3 2
1 4