พิมพ์เส้นทางทั้งหมดจากรากที่มีผลรวมกำหนดใน Binary Tree ใน C++

ในปัญหานี้ เราจะได้รับ Binary Tree และผลรวม S และต้องหาเส้นทางเริ่มจากรากถึงโหนดใดๆ ของต้นไม้ ที่ให้ผลรวมเท่ากับผลรวมที่กำหนด

Input

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

เพื่อหาคำตอบ เราต้องหา preorder traversal ของ binary tree แล้วหาเส้นทางที่บวกกันได้ผลรวมที่กำหนด

โปรแกรมตัวอย่าง

#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 << "Paths with the given sum are : " << endl;
    pathWithSum(root, sum);
    return 0;
}

ผลลัพธ์

Paths with the given sum are -

4 10
4 3 7