ค้นหาคู่ที่มีผลรวมที่กำหนดใน Balanced BST ใน C++

สมมติว่าเรามีแผนผังการค้นหาไบนารีที่สมดุลและผลรวมเป้าหมาย เราต้องกำหนดวิธีการที่ตรวจสอบว่าเป็นคู่ที่มีผลรวมเท่ากับผลรวมเป้าหมายหรือไม่ ในกรณีนี้. เราต้องจำไว้ว่า Binary Search Tree นั้นไม่สามารถเปลี่ยนแปลงได้

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น (9 + 26 =35)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดสแต็ค s1, s2
• เสร็จสิ้น1 :=เท็จ เสร็จสิ้น2 :=เท็จ
• val1 :=0, val2 :=0
• curr1 :=รูท, curr2 :=รูท
• วนซ้ำไม่สิ้นสุด ทำ −
  • ในขณะที่ done1 เป็นเท็จ do −
    • ถ้า curr1 ไม่เท่ากับ NULL แล้ว &ลบ
      • แทรก curr1 ลงใน s1
      • curr1 :=ด้านซ้ายของ curr1
    • มิฉะนั้น
      • ถ้า s1 ว่างเปล่า ดังนั้น −
        • เสร็จ1 :=1
      • มิฉะนั้น
        • curr1 :=องค์ประกอบด้านบนของ s1
        • ลบองค์ประกอบออกจาก s1
        • val1 :=val ของ curr1
        • curr1 :=ด้านขวาของ curr1
        • เสร็จ1 :=1
  • ในขณะที่ done2 ​​เป็นเท็จ do −
    • ถ้า curr2 ไม่เท่ากับ NULL ดังนั้น −
      • แทรก curr2 ลงใน s2
      • curr2 :=ด้านขวาของ curr2
    • มิฉะนั้น
      • ถ้า s2 ว่างเปล่า ดังนั้น −
        • เสร็จ2 :=1
    • มิฉะนั้น
      • curr2 :=องค์ประกอบด้านบนของ s2
      • ลบองค์ประกอบออกจาก s2
      • val2 :=val ของ curr2
      • curr2 :=ด้านซ้ายของ curr2
      • เสร็จ2 :=1
  • ถ้า val1 ไม่เท่ากับ val2 และ (val1 + val2) เหมือนกับเป้าหมาย −
    • คู่พิมพ์ (val1 + val2 =เป้าหมาย)
    • คืนค่าจริง
  • มิฉะนั้น เมื่อ (val1 + val2) <เป้าหมาย จากนั้น −
    • เสร็จสิ้น1:=เท็จ
  • มิฉะนั้น เมื่อ (val1 + val2)> เป้าหมาย จากนั้น −
    • เสร็จสิ้น2 :=เท็จ
  • ถ้า val1>=val2 แล้ว −
    • คืนค่าเท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 100
class TreeNode {
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data) {
         val = data;
         left = NULL;
         right = NULL;
      }
};
bool isPairPresent(TreeNode* root, int target) {
   stack<TreeNode*> s1, s2;
   bool done1 = false, done2 = false;
   int val1 = 0, val2 = 0;
   TreeNode *curr1 = root, *curr2 = root;
   while (true) {
      while (done1 == false) {
         if (curr1 != NULL) {
            s1.push(curr1);
            curr1 = curr1->left;
         }
         else {
            if (s1.empty())
               done1 = 1;
            else {
               curr1 = s1.top();
               s1.pop();
               val1 = curr1->val;
               curr1 = curr1->right;
               done1 = 1;
            }
         }
      }
      while (done2 == false) {
         if (curr2 != NULL) {
            s2.push(curr2);
            curr2 = curr2->right;
         }
         else {
            if (s2.empty())
               done2 = 1;
            else {
               curr2 = s2.top();
               s2.pop();
               val2 = curr2->val;
               curr2 = curr2->left;
               done2 = 1;
            }
         }
      }
      if ((val1 != val2) && (val1 + val2) == target) {
         cout << "Pair Found: " << val1 << " + " << val2 << " = " << target << endl;
         return true;
      }
      else if ((val1 + val2) < target)
         done1 = false;
      else if ((val1 + val2) > target)
         done2 = false;
      if (val1 >= val2)
         return false;
   }
}
int main() {
   TreeNode* root = new TreeNode(16);
   root->left = new TreeNode(11);
   root->right = new TreeNode(21);
   root->left->left = new TreeNode(9);
   root->left->right = new TreeNode(13);
   root->right->left = new TreeNode(17);
   root->right->right = new TreeNode(26);
   int target = 35;
   cout << (isPairPresent(root, target));
}

อินพุต

TreeNode* root = new TreeNode(16);
root->left = new TreeNode(11);
root->right = new TreeNode(21);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(13);
root->right->left = new TreeNode(17);
root->right->right = new TreeNode(26);

ผลลัพธ์

Pair Found: 9 + 26 = 35
1