4

与えられた N 分木が、木のルート ノードを通る線に対して対称かどうかを調べます。二分木の場合は簡単です。ただしN分木の場合は難しそうです

4

5 に答える 5

6

この問題について考える 1 つの方法は、ツリーの反射が再帰的に定義されている場合、それ自体が反射である場合、ツリーは対称であることに注意することです。

  1. 空の木の反射はそれ自体です。
  2. ルート r と子 c1、c2、...、cn を持つツリーの反映は、ルート r と子reflect(cn)、...、reflect(c2)、reflect(c1) を持つツリーです。

次に、ツリーの反射を計算し、それが元のツリーと等しいかどうかを確認することで、この問題を解決できます。これも再帰的に実行できます。

  1. 空のツリーは、それ自体に等しいだけです。
  2. ルート r と子 c1、c2、...、cn を持つツリーは、他のツリーが空ではなく、ルート r を持ち、n 個の子を持ち、c1、...、と等しい子を持つ場合、別のツリー T と等しくなります。 cn の順で。

もちろん、比較を行う前にツリーの完全なコピーを作成するため、これは少し非効率的です。メモリ使用量は O(n + d) です。ここで、n はツリー内のノード数 (コピーを保持するため)、d はツリーの高さ (再帰トム チェックでスタック フレームを保持するため) です。d = O(n) であるため、これは O(n) メモリを使用します。ただし、各フェーズが各ノードを 1 回だけ訪問するため、O(n) 時間で実行されます。

これを行うよりスペース効率の良い方法は、次の再帰的な定式化を使用することです。

1. The empty tree is symmetric.
2. A tree with n children is symmetric if the first and last children are mirrors, the second and penultimate children are mirrors, etc.

次に、次のように 2 つのツリーをミラーとして定義できます。

  1. 空の木は自分自身の鏡にすぎません。
  2. ルート r と子 c1、c2、...、cn を持つツリーは、ルート t と子 d1、d2、...、dn を持つツリーのミラーです。r = t の場合、c1 は dn のミラーであり、c2 はdn-1 などのミラー。

このアプローチも線形時間で実行されますが、ツリーの完全なコピーは作成されません。したがって、メモリ使用量は O(d) のみです。ここで、d はツリーの深さです。これは最悪の場合 O(n) ですが、おそらくはるかに優れています。

于 2011-01-31T20:38:44.987 に答える
1

左側のサブツリーで順番にツリートラバーサル（ノード左右）を実行し、リストに保存します。次に、右側のサブツリーで別の順序どおりのツリートラバーサル（ノード右左）を実行し、リストに保存します。次に、2つのリストを比較するだけです。それらは同じである必要があります。

于 2011-12-24T09:45:17.380 に答える
0

スタックを取得する ルート ノードのトラバースを開始するたびに、関数を再帰的に呼び出して、左のサブツリーの要素を特定のレベルで 1 つずつプッシュします。グローバル変数を維持し、左のサブツリーがスタックにプッシュされるたびにその値を更新します。(左のサブツリーへの再帰呼び出しの後)右のサブを再帰的に呼び出し、正しい一致ごとにポップします。左右対称にチェック。

最後に、スタックが空の場合、つまり、すべての要素が処理され、スタックの各要素がポップアウトされました..完了です!

于 2011-10-10T18:25:33.437 に答える
-1

難しくありません。この質問でゴルフをします。私は 7 点でした... 誰か良くなった人はいますか?

data Tree = Tree [Tree]
symmetrical (Tree ts) =
    (even n || symmetrical (ts !! m)) &&
    all mirror (zip (take m ts) (reverse $ drop (n - m) ts))
    where { n = length ts; m = n `div` 2 }
mirror (Tree xs, Tree ys) =
    length xs == length ys && all mirror (zip xs (reverse ys))
于 2010-02-23T04:50:33.750 に答える