BSTの各内部ノードに子がXNUMXつだけあるかどうかを確認します


難易度 簡単に
よく聞かれる アクセンチュア Amazon (アマゾン) モノタイプソリューション PayPal シノプシス
二分探索木 二分木

問題文

「BSTの各内部ノードに子がXNUMXつだけあるかどうかを確認する」問題は、二分探索木の事前順序探索が与えられていることを示しています。 また、すべての非リーフノードに子がXNUMXつだけ含まれているかどうかを確認する必要があります。 ここでは、指定された入力のすべてのノードが異なる値を持っていることも考慮します。

BSTの各内部ノードに子がXNUMXつだけあるかどうかを確認します

 

Preorder Traversal: 6 15 7 9 11
Yes

説明: 上の画像でわかるように、指定されたプレオーダートラバーサルを持つツリーには、内部ノードごとにXNUMXつの子があります。 したがって、出力はyesです。

BSTの各内部ノードに子がXNUMXつだけあるかどうかを確認するアプローチ

プレオーダートラバーサル ルートが優先され、左右のサブツリーの前に出力されることを意味します。 したがって、ルートの後の要素は、ルートよりも小さいか大きいかのいずれかです。 したがって、特定のシーケンスがの事前注文であるかどうかを確認する必要がある場合 二分探索木。 XNUMXつのネストされたループを使用して、指定されたシーケンスでバイナリ検索ツリーを作成できるかどうかを確認できます。

素朴なアプローチ

すでに説明したように、そのプレオーダートラバーサルには、上部と左右のサブツリーが出力された後にルートが含まれます。 これでこの操作は完了です 再帰的に ツリー内のすべてのノードがカバーされるまで。 したがって、指定されたシーケンスがBSTを表すかどうかを確認できます。外側のループを使用してルートを選択する、XNUMXつのネストされたループを実行します。 そして、ネストされたループは、その後の要素がその左右のサブツリーを表すことができるかどうかをチェックします。 そのために、特定のインデックスまで、すべての要素が選択された要素よりも小さいかどうかを確認します。 そして、その後の要素は、選択された要素よりも大きくなります。 これで、ユースケースに従ってこのアプローチを変更できます。

BSTの各内部ノードに子が2つだけあるかどうかを確認するために、アルゴリズムを変更する方法を見てみましょう。 BSTの内部の子に子がXNUMXつだけある場合。 これは、各内部ノードが左サブツリーまたは右サブツリーのいずれかを持つことができることを意味します。 両方のサブツリーが同時に含まれることはありません。 したがって、私たちのアルゴリズムを要約します。 XNUMXつのネストされたループを使用し、外側のループが要素を選択します。 次に、ネストされたループを使用して、その後に来る要素がサブツリーのいずれかに属しているかどうかを確認します。 以前は、要素がルートよりも小さい前に、要素がルートよりも大きい特定のインデックスを持っていました。 現在、そのようなインデックスは見つかりません。 ただし、この方法は、多項式時間の複雑さがO(N ^ XNUMX)であるため、十分に効率的ではありません。

効率的なアプローチ

これまで、この問題に従って、任意のノードのすべての子が現在のノードよりも小さいか大きいかのいずれかになることを1つのポイントで明確にしました。 したがって、BSTの各内部ノードに子がXNUMXつだけあるかどうかを確認するために、現在のノードの次のプレオーダーサクセサを見つけます。 次に、現在のノードの最後のプレオーダーサクセサを見つけます。 両方のサクセサが現在のノードよりも小さいか、現在のノードよりも大きい場合。 次に、要素のXNUMXつが現在のノードよりも小さいため、現在のノードに左と右の両方のサブツリーがあることがわかります。 そして、別のノードが現在のノードよりも大きくなっています。 したがって、要件に従ってfalseまたは-XNUMXを返します。

コード

BSTの各内部ノードに子がXNUMXつだけあるかどうかを確認するC ++コード

#include<bits/stdc++.h>
using namespace std;

bool checkIfALlInternalNodesHaveSingleChild(vector<int> preorder, int i){
    int n = preorder.size();
    if(i==n-1)return true;
    int next = preorder[i+1] - preorder[i];
    int lst = preorder[n-1] - preorder[i];
    int prod = next*lst;
    if(prod<0)
    return false;
    return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
}

int main()
{
    int n;cin>>n;
    vector<int> preorder(n);
    for(int i=0;i<n;i++)cin>>preorder[i];
    cout<<(checkIfALlInternalNodesHaveSingleChild(preorder, 0) ? "Yes" : "No");
}
5
6 15 7 9 11
Yes

BSTの各内部ノードに子がXNUMXつだけあるかどうかを確認するJavaコード

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  static boolean checkIfALlInternalNodesHaveSingleChild(int preorder[], int i){
      int n = preorder.length;
      if(i==n-1)return true;
      int next = preorder[i+1] - preorder[i];
      int lst = preorder[n-1] - preorder[i];
      int prod = next*lst;
      if(prod<0)
      return false;
      return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int preorder[] = new int[n];
      for(int i=0;i<n;i++)preorder[i] = sc.nextInt();
      boolean answer = checkIfALlInternalNodesHaveSingleChild(preorder, 0);
      System.out.print(answer == true ? "Yes" : "No");
  }
}
5
6 15 7 9 11
Yes

複雑さの分析

時間の複雑さ

O(N)、プレオーダー配列をトラバースしたばかりなので。 また、プレオーダー配列にはN個の要素があるため、時間計算量は線形になります。

スペースの複雑さ

O(N)、再帰スタックに必要なスペース、およびサイズNの入力配列を使用してプレオーダーシーケンスを格納しました。