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