Tìm một cặp có tổng cho trước trong BST Cân bằng trong C ++

Giả sử chúng ta có một cây tìm kiếm nhị phân cân bằng và một tổng đích, chúng ta phải xác định một phương pháp để kiểm tra xem nó có phải là một cặp có tổng bằng với tổng đích hay không. Trong trường hợp này. Chúng ta phải lưu ý rằng Cây tìm kiếm nhị phân là bất biến.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là (9 + 26 =35)

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định các ngăn xếp s1, s2
• done1:=false, done2:=false
• val1:=0, val2:=0
• curr1:=root, curr2:=root
• vòng lặp vô hạn, do -
  • while done1 là false, do -
    • nếu curr1 không bằng NULL, thì &trừ
      • chèn curr1 vào s1
      • curr1:=left of curr1
    • Mặt khác
      • nếu s1 trống, thì -
        • done1:=1
      • Mặt khác
        • curr1:=phần tử trên cùng của s1
        • xóa phần tử khỏi s1
        • val1:=val của curr1
        • curr1:=right of curr1
        • done1:=1
  • while done2 ​​là false, do -
    • nếu curr2 không bằng NULL, thì -
      • chèn curr2 vào s2
      • curr2:=right of curr2
    • Mặt khác
      • nếu s2 trống, thì -
        • done2:=1
    • Mặt khác
      • curr2:=phần tử trên cùng của s2
      • xóa phần tử khỏi s2
      • val2:=val của curr2
      • curr2:=left of curr2
      • done2:=1
  • nếu val1 không bằng val2 và (val1 + val2) giống với đích thì -
    • in cặp (val1 + val2 =target)
    • trả về true
  • ngược lại khi (val1 + val2)
  • done1:=false
• ngược lại khi (val1 + val2)> target, thì -
  • done2:=false
• nếu val1> =val2, thì -
  • trả về false

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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);

Đầu ra

Pair Found: 9 + 26 = 35
1