ルートとリーフパスのペアがあり、合計がC++のルートのデータと等しいかどうかを確認します

この問題では、二分木が与えられます。そして、合計がルートのデータに等しいリーフパスへのルートにペアがあるかどうかを見つける必要があります。

ペアの値の合計がルートノードの値と等しくなるように、ルートノードとリーフノードの間にノードのペアが存在するかどうかを確認する必要があります。

問題を理解するために例を見てみましょう。

入力：

出力： はい

説明：

ルートノード値7

合計値がルートノード（2、5）、（1、6）に等しいペア。

ソリューションアプローチ：

ツリーをトラバースし、ハッシュを使用してペアを見つける必要があります。

このために、hashTableとトラバースツリーを作成します。データをハッシュテーブルに挿入し、他の要素との合計がルートと等しいかどうかを確認します。

最後に、ペアが見つからない場合は、falseを返します。

ペアが見つかった場合は、trueを返します。

ソリューションの動作を説明するプログラム

例

#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;
}

出力

Pair with sum equal to root value found