Invert Binary Tree
レベル順に配列 tree に格納された二分木が与えられます。根はインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあり、-1 は空の位置を示します。また、配列の末尾に余分な -1 が含まれる場合があります。
木を反転します。つまり、すべてのノードの左の子と右の子を入れ替え、木全体を鏡像にします。末尾に -1 がない形式で、反転した木を同じ形式で返してください。
関数
- treeinteger-array
- 二分木をレベル順に並べたもので、空の位置は -1 で示します
- 戻り値integer-array
- 末尾に -1 の要素を付けずに、レベル順に並べた左右反転した木
制約
1 ≤ tree.length ≤ 16383- 各
tree[i]は-1、または0 ≤ tree[i] ≤ 1000を満たす値です。 tree[0]が-1になることは決してないため、ツリーには少なくとも1つのノードがあります。- 配列の末尾には、最後のノードより後に余分な
-1の要素が含まれている場合があります。 - 空の位置の子は両方とも空で、深さは最大でも
14です。
例
- 入力
- tree = [5, 3, 8, 1, 4, -1, 9]
- 出力
- [5, 8, 3, 9, -1, 4, 1]
- 説明
- ルートの子である
3と8が位置を入れ替えます。その下では、3の下にあった1と4が4と1として戻り、右の子9だけを持っていた8は、今度はそれを左に持ちます。
- 入力
- tree = [2, 7, -1, 6]
- 出力
- [2, -1, 7, -1, -1, -1, 6]
- 説明
2、7、6の連鎖は左に傾き、その鏡像は右に傾きます。7はインデックス1からインデックス2へ、6はインデックス3からインデックス6へ移動するため、答えは入力より長くなり、最後のノードより前の空いている各位置には-1が入ります。
- 入力
- tree = [1, -1, -1]
- 出力
- [1]
- 説明
- 単一のノードは、それ自体が鏡像です。2つの
-1のエントリはパディングであり、答えでは末尾にあるすべての-1を取り除きます。
提出時に隠しテスト+14件
発展問題
反転したコピーを作成せずに、同じインデックスのペアを使って、木がそれ自身の鏡像かどうかをどのように確認しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ルートはインデックス
0のままです。鏡像の木では、その左の子はどこに移動するでしょうか？親がどこに移動したかを踏まえて、ノードの移動先を考えてみましょう。インデックス
srcのノードがインデックスdstに移動すると、その左の子は2*dst+2に、右の子は2*dst+1に移動します。各ノードは元のレベルにとどまるため、レベル全体に切り上げた出力には常に十分な余裕があります。出力を
-1で埋めてから、(0, 0)から始まるペアのキューを使って走査します。各ペアについて値をコピーし、実際の子ノードを入れ替えた転送先とともにキューに追加します。最後に、末尾の-1の項目を取り除きます。
解説
ツリーをミラーリングするとは、すべてのノードで左右のサブツリーを入れ替え、末端までそれを繰り返すことです。ノードオブジェクトを使う場合は、ノードごとに1回入れ替えます。この配列表現では、ノードの位置はそのインデックスなので、2つのサブツリーを入れ替えるには、それらの中にあるすべてのノードを移動させる必要があります。新しい配列に答えを作り、走査中にインデックスの組、つまりノードが現在ある位置と移動先の位置を引き継ぎながら、各ノードを鏡像位置へそのままコピーします。
各ノードを鏡像のインデックスに配置する再帰
考え方
まず、配列内の移動方法を確認しましょう。インデックス i のノードは、左の子を 2*i+1 に、右の子を 2*i+2 に持ちます。子が実在するのは、そのインデックスが配列内にあり、そこにある値が -1 ではない場合だけです。[5, 3, 8, 1, 4, -1, 9] では、ルート 5 はインデックス 1 と 2 に 3 と 8 を持ち、インデックス 2 の 8 は、5 に空の左の位置を持ち、6 に 9 を持ちます。
次に、左右反転です。ルートはインデックス 0 のままです。ノードの左部分木は、その鏡像における右部分木になり、右部分木は左部分木になります。つまり、インデックス src のノードが答えのインデックス dst に配置されるなら、その左の子は 2*dst+2 に、右の子は 2*dst+1 に配置されます。place(src, dst) を書きます。値をコピーし、次に place(2*src+1, 2*dst+2) と place(2*src+2, 2*dst+1) を呼び出します。空の位置ならすぐに戻ります。最初の例では、インデックス 1 の 3 は 2 に配置されるため、その左の子 1 は 6 に、右の子 4 は 5 に配置されます。
ノードのレベルは変わらないため、反転後のインデックスは元と同じレベル内に収まります。長さを完全なレベル数（1, 3, 7, 15, ...）に切り上げ、その数だけ -1 で埋め、最後に末尾の -1 の要素を削除します。2つ目の例では、長さ 4 は 7 に切り上げられ、インデックス 6 の 6 を配置する余地ができます。
各ノードは1回ずつ配置され、出力の埋め込みと末尾の削除もそれぞれ1回なので、長さ n の配列に対する時間計算量は O(n) です。出力には O(n) のメモリを使い、呼び出しスタックは O(h) です。ここでは最大14フレームであり、この問題で再帰が安全に使える理由です。
アルゴリズム
- 長さを
size = 2^k - 1まで切り上げ、そのサイズの出力を-1で埋めます。 place(src, dst)を記述します。srcが末尾を過ぎているか、tree[src]が-1の場合は、戻ります。- それ以外の場合は
out[dst] = tree[src]を設定し、続けてplace(2*src+1, 2*dst+2)とplace(2*src+2, 2*dst+1)を呼び出します。 place(0, 0)を呼び出し、末尾の-1の要素を削除して、出力を返します。
def invertTree(tree):
n = len(tree)
size = 1
while size < n: # round up to whole levels, so every mirrored index fits
size = 2 * size + 1
out = [-1] * size
def place(src, dst):
if src >= n or tree[src] == -1:
return
out[dst] = tree[src]
place(2 * src + 1, 2 * dst + 2) # the left subtree goes to the right
place(2 * src + 2, 2 * dst + 1) # the right subtree goes to the left
place(0, 0)
last = size - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]インデックスのペアを格納したキューを使う幅優先探索
考え方
同じペアを再帰なしで使えます。キューに(0, 0)を入れます。これはルートと、そのルートが移される位置です。先頭からペア(src, dst)を取り出し、tree[src]をout[dst]にコピーして、実際に存在する各子について、入れ替え先を対応させてキューに追加します。左の子2*src+1には2*dst+2を、右の子2*src+2には2*dst+1を対応させます。
これは典型的な反復による反転です。ノードオブジェクトを使う場合は、キューからノードを取り出し、その2つの子を入れ替えてからキューに追加します。ここでは、配列では2つの部分木全体を一度に入れ替えられないため、代わりに入れ替え先のインデックスに書き込みます。実際に存在する各ノードは、そのノードが属する正確な位置を持って一度だけキューに入るので、出力にはすべてのノードが鏡像の位置に格納されます。最初の例では、ペアは(0, 0)、(1, 2)、(2, 1)、(3, 6)、(4, 5)、(6, 3)の順になります。
時間計算量はO(n)です。キューが保持するのは最大でも1レベル分と少しで、最も幅の広いレベルの幅をwとするとO(w)です。これに加えてO(n)の出力領域が必要です。呼び出しスタックがあふれることはないため、この方法は深いポインタベースの木にも変更なしで適用できます。
アルゴリズム
- 長さをレベル単位で切り上げ、そのサイズの出力を
-1で埋めます。 - ペア
(0, 0)をキューに入れます。 - 先頭からペア
(src, dst)を取り出し、out[dst] = tree[src]を設定します。 - 各子が配列の範囲内にあり、
-1でない場合、(2*src+1, 2*dst+2)と(2*src+2, 2*dst+1)をキューに入れます。 - キューが空になったら、末尾の
-1エントリを削除し、出力を返します。
def invertTree(tree):
n = len(tree)
size = 1
while size < n: # round up to whole levels, so every mirrored index fits
size = 2 * size + 1
out = [-1] * size
queue = [(0, 0)] # pairs: index in tree, index of its mirrored spot in out
head = 0
while head < len(queue):
src, dst = queue[head]
head += 1
out[dst] = tree[src]
left, right = 2 * src + 1, 2 * src + 2
if left < n and tree[left] != -1:
queue.append((left, 2 * dst + 2)) # the left child goes to the right
if right < n and tree[right] != -1:
queue.append((right, 2 * dst + 1)) # the right child goes to the left
last = size - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]
落とし穴と境界ケース
ミラーリングの処理自体は簡潔に説明できます。バグの原因は配列にあります。サイズ、末尾、そして2つの要素を入れ替えると実際に何が移動するかです。
tree[2*i+1]とtree[2*i+2]をその場で入れ替えること。これで2つの値は入れ替わりますが、その下にある部分木は入れ替わりません。最初の例でインデックス1と2を入れ替えると、1と4は8の下にぶら下がったままになります。- 出力を入力と同じ長さにすること。2番目の例の
6のように、ミラーリングされたノードが入力の最後のインデックスを越えた位置に来ることがあります。出力のサイズはレベル全体を収められるようにします。 - 末尾を切り詰め忘れること。パディングされた入力でも、ミラーリング後の木が入力より早く終わる場合でも、答えの末尾に
-1は付きません。 - 配列全体を逆順にすること。これではレベルが混ざり、最後の葉が根になってしまいます。
- 境界チェックを省略すること。配列が最後のノードの直後で終わる場合があるため、子のインデックスが入力の範囲を越えることがあります。
- 配列の開始位置が1であるLuaとRで、オフセットを取り違えること。
2*i+1の計算ではインデックスを0始まりのままにし、tree[i + 1]を読み取ります。
よくある質問4
二分木を反転するとはどういう意味ですか？
二分木を反転すると、鏡像になります。各ノードで、左部分木と右部分木が入れ替わります。根はそのままで、最も左の葉は最も右になり、左方向の連なりは右方向の連なりになります。2回反転すると、元の木に戻ります。
二分木を反転する時間計算量はどれくらいですか？
各ノードは1回ずつ訪問されるため、時間計算量は O(n) です。再帰的な解法では深さが h の木に対してスタック領域を O(h) 使用し、キューを使う解法では最も幅の広いレベルに対して O(w) 使用します。この配列版では、答え自体が新しい配列であり、これにより O(n) が追加されます。
再帰を使わずに二分木を反転するには、どうすればよいでしょうか？
キューまたはスタックを使います。ルートから始め、ノードを取り出すたびに左右の子を入れ替えて、その子ノードを追加します。構造がどのような順序でノードを取り出しても、各ノードの入れ替えは一度ずつ行われます。配列形式では、代わりにインデックスのペアをキューに入れ、各ノードを鏡像となる位置に直接書き込みます。
二分木を反転すると、各レベルが逆順になるのはなぜですか？
鏡映すると左右がどこでも反転するため、各レベルのノードは逆順に並びます。レベル順の格納では、各レベルに対応する配列のスライスを逆順にすることを意味します。最初の例のスライス [1, 4, -1, 9] は [9, -1, 4, 1] になります。最後のレベルを -1 で埋めてから各レベルを逆順にする方法は、配列がこの形式で格納されている場合にのみ機能する、3つ目の O(n) の解法です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def invertTree(tree):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
tree = [5, 3, 8, 1, 4, -1, 9]
期待値
[5, 8, 3, 9, -1, 4, 1]