In tất cả đường đi từ gốc có tổng cho trước trong cây nhị phân C++

Cho cây nhị phân và số S. Tìm đường đi từ gốc đến nút bất kỳ có tổng bằng S.

Đầu vào:

Sum = 14 Output: path: 4 10 ; 4 3 7

Giải pháp: Duyệt tiền thứ tự (preorder), giữ tổng tích lũy và đường đi hiện tại. Khi tổng = S, in đường đi.

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int key;
    struct Node *left, *right;
};
Node* insertNode(int key){
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
void printPathsUtilSum(Node* curr_node, int sum, int sum_so_far, vector<int> &path){
    if (curr_node == NULL) return;
    sum_so_far += curr_node->key;
    path.push_back(curr_node->key);
    if (sum_so_far == sum){
        for (int i = 0; i < path.size(); i++) cout << path[i] << "\t";
        cout << endl;
    }
    if (curr_node->left != NULL) printPathsUtilSum(curr_node->left, sum, sum_so_far, path);
    if (curr_node->right != NULL) printPathsUtilSum(curr_node->right, sum, sum_so_far, path);
    path.pop_back();
}
void pathWithSum(Node *root, int sum){
    vector<int> path;
    printPathsUtilSum(root, sum, 0, path);
}
int main(){
    Node *root = insertNode(4);
    root->left = insertNode(10);
    root->right = insertNode(3);
    root->right->left = insertNode(7);
    root->right->right = insertNode(1);
    root->left->left = insertNode(8);
    root->left->right = insertNode(6);
    int sum = 14;
    cout << "Các đường đi có tổng cho trước:\n";
    pathWithSum(root, sum);
    return 0;
}

Kết quả

4 10
4 3 7