3

巨大でメモリに配置できない二分木が与えられた場合、その木が鏡像であるかどうかをどのように確認しますか。

インタビューの質問としてこれを得た

4

3 に答える 3

4

ツリーが別のツリーの鏡像である場合、あるツリーの順序どおりのトラバーサルは別のツリーの逆になります。

したがって、最初のツリーで順不同のトラバーサルを実行し、別のツリーで逆順のトラバーサルを実行して、すべての要素が同じかどうかを確認します。

于 2015-06-23T06:33:53.763 に答える
2

もちろん、この返信を完全に信用することはできません。私の同僚の何人かは、いくつかの仮説を立てたり、私の最初のアイデアに穴をあけたりするのを手伝ってくれました。彼らに感謝します！

仮定

  • ツリー全体をメモリに保持することはできないため、再帰を使用するのは理想的ではありません。簡単にするために、メモリ内に最大 2 つのノードしか保持できないと仮定しましょう。

  • ツリーのレベルの総数であるnを知っています。

  • 文字または行の位置に関して、データに対してシークを実行できます。

  • ディスク上のデータは深度順に並べられています。つまり、ディスク上の最初のエントリはルートであり、次の 2 つがその子であり、次の 4 つがその子の子であり、以下同様です。

  • データが完全にミラーリングされている場合とそうでない場合があります。特に指定のない限り、非空白データと組み合わされた空白データは「許容可能」と見なされます。

  • 値が同等かどうかを比較できる限り、任意のデータ型を自由に使用できます。オブジェクトの等価性のテストは理想的ではない可能性があるため、プリミティブを比較していると仮定しましょう。

  • 「ミラーリング」とは、ルートの子の間でミラーリングされることを意味します。別の用語を使用すると、祖父母の左の子はその右の子にミラーリングされ、左の子 (親) の左の子は祖父母の右の子の右の子にミラーリングされます。これを下のグラフに示します。一致する記号は、チェックするミラーリングを表します。

                G
      P*         P*
   C1&  C2^   C3^ C4&

アプローチ

ディスクから読み取るときに、各レベルで予想されるノードの数を知っています - 2 kの倍数です。ツリーの深さの合計と各レベルのノードの数を反復する二重ループを確立できます。この内部では、最も外側の値が等しいかどうかを単純に比較し、等しくない値が見つかった場合は短絡することができます。

2 kの倍数を使用して、外側の各位置の位置を決定できます。任意のレベルの左端の子は常に 2 kになり、任意のレベルの右端の子は常に 2 k+1 -1 になります。

小さな証明: レベル 1 の最も外側のノードは 2 と 3 です。2 1 = 2、2 1+1 -1 = 2 2 -1 = 3。レベル 2 の最も外側のノードは 4 と 7 です。2 2 = 4, 2 2+1 -1 = 2 3 -1 = 7. これを n 番目のケースまで拡張できます。

疑似コード

int k, i;
for(k = 1; k < n; k++) { // Skip root, trivially mirrored
    for(i = 0; i < pow(2, k) / 2; i++) {
        if(node_retrieve(i + pow(2, k)) != node_retrieve(pow(2, (k+1)-i)) {
            return false;
        }
     }
 }
 return true;

考え

この種の質問は面接での素晴らしい質問です。おそらく、彼らはあなたがこの問題にどのように取り組むかを見たいと思っているからです。このアプローチはひどいかもしれませんし、真っ白かもしれませんが、雇用主はあなたに時間をかけて紙やホワイトボードに絵を描いてもらい、データがどのように保存されているか、どのように読み取れるか、何を読むことができるかについて質問することを望んでいます。シークなどに制限があります。

インタビュアーが興味を持っているのはコーディングの側面ではなく、問題解決の側面です。

于 2012-04-05T07:31:20.180 に答える
0

再帰は簡単です。 

struct node {
        struct node *left;
        struct node *right;
        int payload;
        };

int is_not_mirror(struct node *one, struct node *two)
{
if (!one && !two) return 0;
if (!one) return 1;
if (!two) return 1;
if (compare(one->payload, two->payload)) return 1;
if (is_not_mirror(one->left, two->right)) return 1;
if (is_not_mirror(one->right, two->left)) return 1;
return 0;
}
于 2012-04-04T19:23:06.743 に答える