Tìm xem có một cặp trong thư mục gốc đến một đường dẫn lá với tổng bằng với dữ liệu của thư mục gốc trong C ++

Trong bài toán này, chúng ta được đưa ra một Cây nhị phân. Và chúng ta cần tìm xem có một cặp từ gốc đến đường dẫn lá với tổng bằng dữ liệu của gốc hay không.

Chúng tôi cần kiểm tra xem có tồn tại một cặp nút nằm giữa nút gốc đến nút lá sao cho tổng giá trị của các cặp bằng giá trị của nút gốc hay không.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào:

Đầu ra: Có

Giải thích:

Giá trị nút gốc 7

Các cặp có tổng giá trị bằng nút gốc, (2, 5), (1, 6).

Phương pháp tiếp cận giải pháp:

Chúng ta cần đi qua cây và tìm các cặp bằng cách sử dụng băm.

Đối với điều này, chúng tôi sẽ tạo một hashTable và cây ngang. Chèn dữ liệu vào bảng băm và sau đó kiểm tra xem tổng của nó với các phần tử khác có bằng gốc hay không.

Và cuối cùng, nếu chúng tôi không tìm thấy cặp nào, hãy trả về false.

Nếu các cặp được tìm thấy, trả về true.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

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> &amp;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;
}

Đầu ra

Pair with sum equal to root value found