ค้นหาว่ามีคู่ในรูทไปยังเส้นทางลีฟโดยมีผลรวมเท่ากับข้อมูลของรูทใน C++ . หรือไม่

ในปัญหานี้ เราได้รับ Binary Tree และเราจำเป็นต้อง ค้นหาว่ามีคู่ในเส้นทางรากไปยังเส้นทางใบไม้ที่มีผลรวมเท่ากับข้อมูลของรากหรือไม่

เราจำเป็นต้องตรวจสอบว่ามีโหนดคู่หนึ่งที่อยู่ระหว่างโหนดรูทถึงโหนดปลายสุดหรือไม่ โดยที่ผลรวมของค่าของคู่นั้นเท่ากับค่าของโหนดรูท

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล:

ผลลัพธ์: ใช่

คำอธิบาย:

ค่าโหนดรูท 7

จับคู่กับค่าผลรวมเท่ากับรูทโหนด (2, 5), (1, 6)

แนวทางแก้ไข:

เราจำเป็นต้องสำรวจต้นไม้และหาคู่โดยใช้การแฮช

สำหรับสิ่งนี้ เราจะสร้าง hashTable และทรีสำรวจ แทรกข้อมูลลงใน hashtable จากนั้นตรวจสอบว่าผลรวมของข้อมูลกับองค์ประกอบอื่นเท่ากับรูทหรือไม่

และสุดท้าย หากเราไม่พบคู่ ให้คืนค่า เท็จ

หากพบคู่ ให้คืนค่า 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