だから、私は次のようになる明らかなブルートフォースアルゴリズムを持っています
int isSubtree (binTree *S, binTree *T)
{
if (S == NULL)
return 0;
return (isEqual (S,T) || isSubtree (S->left, T) || isSubtree (S->right, T));
}
int isEqual (binTree *S, bintree *T)
{
if (S==NULL && T==NULL)
return 1;
if (S==NULL || T==NULL)
return 0;
if (S->val == T->val)
return isEqual(S->left,T->left) && isEqual (S->right,T->right);
else
return 0;
}
しかし、これは O(n²) アプローチです。
次のような別のアプローチがあります。これは O(n) です。最初のツリーを順番どおりにトラバースし、それを配列に格納します。次に、2 番目のツリーをトラバースし、順序どおりに格納します。ここで、2 番目の配列が最初の配列のサブ配列である場合は、先に進み、先行順序トラバーサルについても同じ手順を繰り返します。両方のクエリの結果が TRUE の場合、ツリーは最初のツリーのサブツリーです。そうでなければ、そうではありません。
次のアルゴリズムが機能するかどうか教えてもらえますか?
そして、この問題に対してよりスペースを最適化したソリューションはありますか?
注: 両方の配列のトラバーサルを保存しているので、2 つの配列が必要ですが、とにかく 1 つの配列でできることはありますか? ツリーの 1 つの順不同トラバーサルを格納し、その配列を使用して、他のツリーをトラバースしながらサブ配列の状態をチェックするように。それとも、余分なスペースはなく、O(n) 時間の複雑さでしょうか?
注: サブ配列とは、要素が連続して発生する必要があることを意味します。
{2,3,5} is a subarray of {1,2,3,5} but not a subarray of {1,2,3,4,5}