Kiểm tra cặp nút trên đường gốc đến lá tổng bằng giá trị gốc trong C++

Cho cây nhị phân. Nhiệm vụ: kiểm tra có cặp nút trên đường từ gốc đến lá nào đó có tổng bằng giá trị nút gốc không.

Ví dụ:

Đầu vào:

Đầu ra: Yes

Giải thích: Giá trị gốc = 7. Các cặp: (2,5), (1,6).

Phương pháp giải

Duyệt cây, dùng hash set lưu giá trị các nút trên đường đi hiện tại. Với mỗi nút, kiểm tra xem (root->data - node->data) có trong set không. Nếu có => tìm thấy cặp. Backtrack: xóa nút khỏi set khi quay lui.

Chương trình minh họa

Ví dụ

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* left, *right;
};

struct Node* newnode(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

bool findSumUntill(Node *node, unordered_set<int> &hashTable, int rootVal) {
    if (node == NULL)
        return false;
    int otherVal = rootVal - node->data;
    if (hashTable.find(otherVal) != hashTable.end())
        return true;
    hashTable.insert(node->data);
    bool isFound = findSumUntill(node->left, hashTable, rootVal) || findSumUntill(node->right, hashTable, rootVal);
    hashTable.erase(node->data);
    return isFound;
}

bool findPairSum(Node *root) {
    unordered_set<int> hashTable;
    return findSumUntill(root->left, hashTable, root->data) || findSumUntill(root->right, hashTable, root->data);
}

int main() {
    struct Node *root = newnode(7);
    root->left = newnode(2);
    root->right = newnode(3);
    root->left->left = newnode(5);
    root->left->right = newnode(9);
    root->left->left->left = newnode(1);
    root->left->left->right = newnode(6);
    root->right->left = newnode(8);
    if (findPairSum(root))
        cout << "Pair with sum equal to root value found";
    else
        cout << "No pairs found";
    return 0;
}

Kết quả

Pair with sum equal to root value found