Symmetric Tree
レベル順に配列 tree に格納された二分木が与えられます。根はインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、配列の末尾に余分な -1 の要素が含まれている場合があります。根を通る垂直線を軸として木がそれ自身の鏡像になっている場合は true を、そうでない場合は false を返してください。形状と値の両方が一致する必要があります。
関数
- treeinteger-array
- レベル順の二分木。空の位置は -1 で表します
- 戻り値boolean
- 木が自身と鏡像関係にある場合は true、そうでない場合は false
制約
1 ≤ tree.length ≤ 32767- 各
tree[i]は-1または0 ≤ tree[i] ≤ 1000を満たす値です。 tree[0]が-1になることは決してないため、ツリーには少なくとも1つのノードがあります。- 配列は、最後のノードの後に余分な
-1の要素が続いている場合があります。 - 空の位置の子は両方とも空であり、深さは最大でも
14です。
例
- 入力
- tree = [1, 2, 2, 3, 4, 4, 3]
- 出力
- true
- 説明
- 木を中央で折りたたみます。インデックス
1と2にある2つの2が重なり、インデックス3と6にある外側の3が重なり、インデックス4と5にある内側の4が重なります。
- 入力
- tree = [1, 2, 2, -1, 3, -1, 3]
- 出力
- false
- 説明
- 両方の
3は親の右側にぶら下がっています。鏡像では、左側の2の右の子（インデックス4）は、右側の2の左の子（インデックス5）と向かい合う必要がありますが、インデックス5は空です。
- 入力
- tree = [4, 6, 6, 5, -1, -1, 9]
- 出力
- false
- 説明
- 形は鏡像になっています。インデックス
3はインデックス6と向かい合い、どちらにもノードがあります。値は5と9で異なるため、この木は対称ではありません。
提出時に隠しテスト+16件
発展問題
形状は左右対称でも、一部の値が異なる場合、木を対称にするには最少でいくつのノード値を変更する必要がありますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ルートの左の子はどのノードと一致する必要がありますか？また、そのノードの左の子はどのノードと一致する必要がありますか？
一度に2つの位置を比較します。両方が空である場合、または両方に同じ値が入り、子が交差している場合、つまり一方の左の子がもう一方の右の子と鏡像になり、一方の右の子がもう一方の左の子と鏡像になります。
(1, 2)から始めて、インデックスのペアをスタックに保持します。ペアを取り出し、両方の位置が空ならスキップし、片方だけが空か値が異なる場合は失敗とし、それ以外の場合は(2*a+1, 2*b+2)と(2*a+2, 2*b+1)を追加します。
解説
対称性とは、ペアに関する性質です。各ノードには、ルートの反対側の鏡映位置にある相手がいて、左の子の相手は右の子です。そのため、ノードをその子自身と比較することはありません。木の左右の部分を同時に反対方向へたどり、各ペアの形と値を比較し、最初に一致しないペアで停止します。
各レベルを逆順のものと比較する
考え方
まず、配列内をどのように移動するかを見てみましょう。インデックス i のノードは、左の子を 2*i+1、右の子を 2*i+2 に持ちます。子が実在するのは、そのインデックスが配列の範囲内にあり、そこにある値が -1 ではない場合だけです。[1, 2, 2, 3, 4, 4, 3] では、ルート 1 の子はインデックス 1 と 2 にあり、インデックス 1 の 2 の子は 3 と 4 にあります。
次に、木をレベルごとに見てみましょう。鏡像では左から右に読んでも右から左に読んでも同じになるため、空の位置も含めて書き出した各レベルは、どちらの方向から読んでも同じでなければなりません。最初の例では、ルートの下のレベルは 2 2 と 3 4 4 3 です。2番目の例では、2 2、続いて -1 3 -1 3 となり、逆順にすると 3 -1 3 -1 になるため、答えは false です。
空の位置も列に残しておく必要があります。空の位置を除くと、2番目の例の最下位レベルは 3 3 となり、条件を満たしてしまいます。そのレベルにある実在する各ノードの子の位置ごとに1つずつ値を書き、空の位置には -1 を入れます。空の位置には子がないため、さらに値を追加する必要はありません。各ノードは1回ずつ訪問されるので、時間計算量は O(n) です。また、一度にメモリに保持するのは1つのレベルだけなので、最も幅の広いレベルの幅を w とすると、空間計算量は O(w) です。
アルゴリズム
- ルートのインデックス
0を含むリストから始めます。 - リスト内の各インデックスについて、左から右へ、両方の子の位置を書き出します。子が存在する場合はその値、空の場合は
-1とします。次のレベルのために、実在する子を集めます。 - 子の位置の並びが逆順にしたものと異なる場合は、
falseを返します。 - 次のレベルに進み、空になるまで繰り返してから、
trueを返します。
def isSymmetric(tree):
n = len(tree)
level = [0] # the real nodes of one level, left to right
while level:
row = [] # the child spots under this level, -1 for an empty one
next_level = []
for i in level:
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
row.append(tree[child])
next_level.append(child)
else:
row.append(-1)
if row != row[::-1]:
return False
level = next_level
return True鏡像ペアに対する再帰
考え方
レベル全体ではなく、2つの部分木を比較します。インデックス 1 から始まるルートの左部分木と、インデックス 2 から始まる右部分木です。2つの位置は、どちらも空であるか、同じ値を持ち、子が交差するように対応しているとき、互いに鏡映になります。一方の左の子はもう一方の右の子と対応し（外側のペア）、一方の右の子はもう一方の左の子と対応します（内側のペア）。
最初の例では、mirrors(1, 2) が2つの 2 を比較し、続いて外側の 3 に対して mirrors(3, 6) を、内側の 4 に対して mirrors(4, 5) を呼び出します。どちらも下に空の位置しかないことを確認し、true を返します。2つ目の例では、mirrors(4, 5) が、インデックス 4 にある 3 と、インデックス 5 にある空の位置を見つけて false を返し、その false が最上位まで伝わります。
各実ノードは最大1つのペアにしか属さないため、時間計算量は O(n) です。呼び出しスタックの深さは木の高さと同じ O(h) で、ここでは最大14フレームです。
アルゴリズム
mirrors(a, b)を記述します。インデックスが末尾を超えているか、-1を保持している場合、その位置は空です。両方の位置が空ならtrueを返し、片方だけが空ならfalseを返します。tree[a]とtree[b]が異なる場合は、falseを返します。- それ以外の場合は、
mirrors(2*a+1, 2*b+2)とmirrors(2*a+2, 2*b+1)を返します。 mirrors(1, 2)を返します。子を持たないルートでは、2つの位置が空になるため、結果はtrueです。
def isSymmetric(tree):
n = len(tree)
def mirrors(a, b):
# Spots a and b must hold the same value, or both be empty.
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a or empty_b:
return empty_a and empty_b
return (tree[a] == tree[b]
and mirrors(2 * a + 1, 2 * b + 2) # outer pair
and mirrors(2 * a + 2, 2 * b + 1)) # inner pair
return mirrors(1, 2)鏡映対の明示的なスタック
考え方
再帰に必要なのは、確認待ちのペアだけです。それらのペアを自分で用意したスタックに保持すれば、呼び出しは不要になります。ペア (1, 2) から始めます。ペアを取り出します。両方の位置が空なら、その下には何もないので次に進みます。片方が空か、値が異なれば、木は対称ではありません。それ以外の場合は、外側のペア (2*a+1, 2*b+2) と内側のペア (2*a+2, 2*b+1) を追加します。
すべてのペアが一致する場合に限り木は対称なので、ペアを確認する順序は関係ありません。スタックを使うと深さ優先順になり、キューを使えばレベル順になりますが、どちらも同じように機能します。3つ目の例では、最初に不一致となるペア (3, 6) で処理が止まります。このペアの値は 5 と 9 です。
ペアを1つ取り出すごとに1組を処理し、各実ノードは高々1組のペアに含まれるため、時間計算量は O(n) です。スタックには、現在の経路の各レベルにつき保留中のペアが約1組保持されるため、空間計算量は O(h) です。また、再帰の深さ制限を気にする必要もありません。
アルゴリズム
- ペア
(1, 2)をスタックにプッシュします。 - ペア
(a, b)をポップします。両方の位置が空（インデックスが末尾を超えている、または-1）の場合は、次のペアに進みます。 - 一方の位置だけが空の場合、または
tree[a]がtree[b]と異なる場合は、falseを返します。 (2*a+1, 2*b+2)と(2*a+2, 2*b+1)をプッシュします。- スタックが空になったら、
trueを返します。
def isSymmetric(tree):
n = len(tree)
stack = [(1, 2)] # pairs of spots that must mirror each other
while stack:
a, b = stack.pop()
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a and empty_b:
continue
if empty_a or empty_b or tree[a] != tree[b]:
return False
stack.append((2 * a + 1, 2 * b + 2)) # outer pair
stack.append((2 * a + 2, 2 * b + 1)) # inner pair
return True
落とし穴と境界ケース
誤答の多くは、比較するノードの組み合わせを間違えるか、空の位置も形の一部であることを忘れています。
- 各部分木を個別に調べる。左部分木だけで対称である必要はありません。
[1, 2, 2, 3, 4, 4, 3]では、部分木2, 3, 4は対称ではありませんが、木全体は対称です。右部分木と鏡映になっている必要があります。 - 子の組み合わせを間違える。一方の左の子は、もう一方の右の子と向き合います。つまり、
(2*a+1, 2*b+2)と(2*a+2, 2*b+1)であり、(2*a+1, 2*b+1)ではありません。 - 値だけを比較する。
[1, 2, 2, -1, 3, -1, 3]から空の位置を取り除くと、どのレベルも両方向で同じように読めますが、木は対称ではありません。レベルごとの行に-1を残すか、ペアのチェックで空かどうかを調べてください。 - 配列の末尾を超えて読み取る。配列の末尾を超えたインデックスは空の位置です。
tree[a]を読み取る前にa < nを確認してください。ノードが1つだけの木には、インデックス1も2もありません。 - 最初に一致したペアで処理を止める。ペアが1組正しいだけでは何も証明できません。すべてのペアを確認した後にのみ
trueを返してください。 - 配列のインデックスが1から始まるLuaとRで、オフセットを取り違える。
2*i+1の計算ではノードのインデックスを0始まりのままにし、tree[i + 1]を読み取ってください。
よくある質問4
Symmetric Tree の時間計算量は何ですか？
各実ノードは1つの鏡像ペアの一部として1回ずつ比較されるため、時間計算量は O(n) です。再帰版とスタック版では、現在の経路上にある未処理のペアのために、追加で O(h) の領域を使用します。レベルごとに処理する版では、1つのレベルをメモリ上に保持するため、最も幅の広いレベルに対して O(w) です。
再帰を使わずに、二分木が対称かどうかを確認するにはどうすればよいですか？
互いに鏡像でなければならないノードのペアをスタックまたはキューに保持し、ルートの2つの子から始めます。ペアを取り出し、不一致があれば失敗とし、それらの子の外側のペアと内側のペアを追加します。不一致がないままスタックが空になれば、木は対称です。
対称な木と同一の木が2つあることの違いは何ですか？
2つの木は、左と左、右と右を比較したときに同一であれば、同一です。木は、左部分木が右部分木の鏡像と同一であれば対称です。そのため比較の組み合わせは入れ替わり、左と右、右と左を比較します。同じペアを確認するコードで、子のペアを入れ替えれば両方の問題を解決できます。
単一のノードを持つ木は対称ですか？
はい。単一のノードには空の子ノードの位置が2つあり、2つの空の位置は互いに対称です。子ノードがちょうど1つだけのルートは決して対称ではありません。その子ノードが空の位置と向き合っているからです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isSymmetric(tree):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
tree = [1, 2, 2, 3, 4, 4, 3]
期待値
true