C++의 균형 BST에서 주어진 합계를 가진 쌍 찾기

균형 이진 탐색 트리와 목표 합이 있다고 가정하고 합이 목표 합과 같은 쌍인지 여부를 확인하는 방법을 정의해야 합니다. 이 경우. 이진 검색 트리는 변경할 수 없음을 명심해야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 (9 + 26 =35)

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 스택 s1, s2 정의
• 완료1 :=거짓, 완료2 :=거짓
• val1 :=0, val2 :=0
• curr1 :=루트, curr2 :=루트
• 무한 루프, do -
  • done1이 거짓일 때 −
    • curr1이 NULL과 같지 않으면 &minus
      • curr1을 s1에 삽입
      • curr1 :=curr1의 왼쪽
    • 그렇지 않으면
      • s1이 비어 있으면 -
        • 완료1 :=1
      • 그렇지 않으면
        • curr1 :=s1의 최상위 요소
        • s1에서 요소 삭제
        • val1 :=curr1의 값
        • curr1 :=curr1의 오른쪽
        • 완료1 :=1
  • done2가 거짓인 동안 −
    • curr2가 NULL과 같지 않으면 -
      • curr2를 s2에 삽입
      • curr2 :=curr2의 오른쪽
    • 그렇지 않으면
      • s2가 비어 있으면 -
        • 완료2 :=1
    • 그렇지 않으면
      • curr2 :=s2의 최상위 요소
      • s2에서 요소 삭제
      • val2 :=curr2의 값
      • curr2 :=curr2의 왼쪽
      • 완료2 :=1
  • val1이 val2와 같지 않고 (val1 + val2)가 target과 같으면 −
    • 인쇄 쌍(val1 + val2 =대상)
    • 참을 반환
  • 그렇지 않으면 (val1 + val2)
  • 완료1 :=거짓
• 그렇지 않으면 (val1 + val2)> target일 때 -
  • 완료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