C++のバイナリ検索ツリーでプレオーダーシーケンスを確認する

数列があるとします。それが二分探索木の正しいプレオーダートラバーサルシーケンスであるかどうかを確認する必要があります。シーケンス内の各番号は一意であると想定できます。次の二分探索木を考えてみましょう-

したがって、入力が[5,2,1,3,6]のような場合、出力はtrueになります

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

• itr：=-1

• 低：=-infinity

• 初期化i：=0の場合、i <プレオーダーのサイズの場合、更新（iを1増やします）、実行-

  • x：=preorder [i]

  • x

    • falseを返す

  • while（itr> =0 and preorder [itr]

    • 低：=preorder [itr]

    • （itrを1減らします）

  • （itrを1増やします）

  • preorder [itr]：=x

• trueを返す

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool verifyPreorder(vector<int<& preorder) {
      int itr = -1;
      int low = INT_MIN;
      for (int i = 0; i < preorder.size(); i++) {
         int x = preorder[i];
         if (x < low)
            return false;
         while (itr >= 0 && preorder[itr] < x) {
            low = preorder[itr];
            itr--;
         }
         itr++;
         preorder[itr] = x;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<int< v = {5,2,1,3,6};
   cout << (ob.verifyPreorder(v));
}

入力

{5,2,1,3,6}

出力

1