C++の平衡二分探索木で与えられた合計を持つペアを見つけます

平衡二分探索木とターゲット合計があるとすると、合計がターゲット合計に等しいペアであるかどうかをチェックするメソッドを定義する必要があります。この場合。二分探索木は不変であることに注意する必要があります。

したがって、入力が次のような場合

その場合、出力は（9 + 26 =35）

これを解決するには、次の手順に従います-

• スタックs1、s2を定義する
• done1：=false、done2：=false
• val1：=0、val2：=0
• curr1：=root、curr2：=root
• 無限ループ、実行-
  • done1がfalseの場合、do −
    • curr1がNULLと等しくない場合、＆minus
      • curr1をs1に挿入します
      • curr1：=curr1の左側
    • それ以外の場合
      • s1が空の場合、-
        • done1：=1
      • それ以外の場合
        • curr1：=s1の最上位要素
        • s1から要素を削除する
        • val1：=curr1のval
        • curr1：=curr1の権利
        • done1：=1
  • done2がfalseの場合、do −
    • curr2がNULLに等しくない場合、-
      • curr2をs2に挿入します
      • curr2：=curr2の権利
    • それ以外の場合
      • s2が空の場合、-
        • done2：=1
    • それ以外の場合
      • curr2：=s2の最上位要素
      • s2から要素を削除する
      • val2：=curr2のval
      • curr2：=curr2の左側
      • done2：=1
  • val1がval2と等しくなく、（val1 + val2）がターゲットと同じである場合、-
    • 印刷ペア（val1 + val2 =ターゲット）
    • trueを返す
  • それ以外の場合、（val1 + val2）
  • done1：=false
• それ以外の場合、（val1 + val2）>ターゲットの場合、-
  • done2：=false
• val1> =val2の場合、-
  • falseを返す

例

理解を深めるために、次の実装を見てみましょう-

#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