Construct Binary Tree from Preorder and Inorder Traversal
同じ二分木の異なる値を列挙した2つの配列 preorder と inorder が与えられます。先行順走査では、ノードを訪問し、次に左部分木、右部分木の順に訪問します。中間順走査では、左部分木、ノード、右部分木の順に訪問します。
木を再構築し、レベル順の配列として返してください。ルートはインデックス 0 に置き、インデックス i の子は 2i+1（左）と 2i+2（右）に置き、空の位置にはそれぞれ -1 を入れます。配列は最後のノードで終わり、末尾に -1 は付きません。
関数
- preorderinteger-array
- 先行順の値：ノード、左部分木、右部分木
- inorderinteger-array
- 中順での値: 左部分木、ノード、右部分木
- 戻り値integer-array
- レベル順の木。空の位置には -1 を使い、末尾に -1 は付けない
制約
1 ≤ preorder.length ≤ 3000inorder.length == preorder.length0 ≤ preorder[i] ≤ 104で、すべての値は異なります。inorderには同じ値が格納されており、どちらの配列も同じ二分木を表しています。- 木の深さは最大でも
14なので、答えに含まれるすべてのインデックスは214-1 = 16383未満です。
例
- 入力
- preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
- 出力
- [7, 3, 4, 0, 9, -1, 6]
- 説明
- 先行順はルートの
7から始まります。これはinorderの位置3にあるため、0, 3, 9は左に、4, 6は右に進みます。4には右の子である6だけがあるため、インデックス5は-1のままです。
- 入力
- preorder = [1, 2, 3]inorder = [2, 3, 1]
- 出力
- [1, 2, -1, -1, 3]
- 説明
- ルートの
1はinorderで最後に来るため、インデックス2は-1です。2, 3のうち、preorder では2が先に並び、inorder ではその後に3が来るため、3はその右の子で、インデックス4にあります。
発展問題
明示的なスタックを使い、preorderを1回走査するだけで、再帰を使わずに木を再構築できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ツリー全体のルートを示す配列はどれですか？また、そのルートはもう一方の配列のどこにありますか？
ルートによって、
inorderは左部分木の値と右部分木の値に分けられます。preorderでは、左部分木の値はルートの直後に並び、その数は左側の値の数と同じです。同じ分割は、すべての部分木の中でも機能します。根の先行順序のインデックスと出力インデックス
hを使って、通りがけ順の範囲lo..hiを再帰的に処理します。根をhに書き込み、その通りがけ順での位置mを見つけてから、左側の部分を2*h+1に、右側の部分を2*h+2に構築します。値から通りがけ順での位置へのマップを使えば、mを1ステップで見つけられます。
解説
先行順走査では、すべての部分木の根がわかります。それぞれの範囲の最初の値が根です。中間順走査では分割位置がわかります。根より前の値は左側へ、後の値は右側へ進みます。両方の半分に対して再帰処理を行うと木を再構築でき、値から中間順走査での位置へのマップを使えば、各根の検索を1ステップで行えます。
ルートを探して再帰的に分割する
考え方
先行順では、左部分木は根の後に続き、値ごとに1つの要素を使います。その数は m-lo 個で、ここで m は根の中間順での位置です。右部分木はその後に続くため、その根は pre+1+(m-lo) にあります。最初の例では左側の部分 0, 3, 9 に値が3つあるので、右部分木は先行順インデックス 4、つまり値 4 から始まります。
深さを最大14に制限すると、すべての出力インデックスは 2^14-1 未満になります。その数だけセルを -1 で埋め、各値をそのインデックスに書き込み、最後に末尾の -1 の要素を削除します。
各中間順の範囲を走査して根を探す処理のコストは O(n·h) です。同じ階層の範囲は重ならないため、1つの階層で走査する要素数は最大 n で、ここでは最大14 × 3000 = 42000ステップです。深さの制限がない場合、道のような形の木では O(n²) になります。
アルゴリズム
2^14-1個の要素を持つoutを作成し、すべて-1にします。build(pre, lo, hi, h)を記述します。lo > hiの場合は戻ります。それ以外の場合は、preorder[pre]をout[h]に書き込みます。inorderをloから走査し、ルートの位置mを見つけます。左部分木にはm-lo個の値があります。build(pre+1, lo, m-1, 2*h+1)とbuild(pre+1+(m-lo), m+1, hi, 2*h+2)を呼び出します。build(0, 0, n-1, 0)を呼び出し、末尾の-1の要素を取り除いて、残りを返します。
def buildTree(preorder, inorder):
out = [-1] * (2 ** 14 - 1) # every index of a depth-14 tree is below 2^14-1
def build(pre, lo, hi, h):
# preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
# it goes to index h of the output.
if lo > hi:
return
value = preorder[pre]
out[h] = value
m = lo
while inorder[m] != value: # find the root in the inorder range
m += 1
left_size = m - lo
build(pre + 1, lo, m - 1, 2 * h + 1)
build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)
build(0, 0, len(inorder) - 1, 0)
last = len(out) - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]位置マップを使って再帰的に分割する
考え方
値はそれぞれ異なるため、inorder 内で各値の位置はちょうど1つです。再帰を始める前に、値から位置へのマップに記録しておけば、各ルートの検索は1ステップで済みます。
マップの構築にはO(n)かかり、その後は各値を定数時間で1回ずつ配置するため、合計時間はO(n)です。マップにはO(n)の領域が必要で、再帰では各レベルにつき1つのフレームを使います。CとRでは値は最大でも10^4なので、10^4+1個の要素を持つ単純な配列をマップとして使えます。
アルゴリズム
inorderの各値からその位置へのマップを作成します。- すべて
-1である2^14-1個の要素を持つoutを作成します。 build(pre, lo, hi, h)では、lo > hiなら戻ります。そうでなければ、preorder[pre]をout[h]に書き込み、マップからその位置mを検索します。build(pre+1, lo, m-1, 2*h+1)とbuild(pre+1+(m-lo), m+1, hi, 2*h+2)で再帰します。build(0, 0, n-1, 0)を呼び出し、末尾の-1要素を取り除いて残りを返します。
def buildTree(preorder, inorder):
position = {value: i for i, value in enumerate(inorder)} # value -> inorder index
out = [-1] * (2 ** 14 - 1) # every index of a depth-14 tree is below 2^14-1
def build(pre, lo, hi, h):
# preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
# it goes to index h of the output.
if lo > hi:
return
value = preorder[pre]
out[h] = value
m = position[value]
left_size = m - lo
build(pre + 1, lo, m - 1, 2 * h + 1)
build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)
build(0, 0, len(inorder) - 1, 0)
last = len(out) - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]
落とし穴と境界ケース
- 右部分木の開始位置を
pre+1+(m-lo)ではなくpre+1+mにすること。最上位の呼び出しのようにloが0の間は動作しますが、範囲の開始位置が後ろになると動作しなくなります。 - 空き位置を詰めてしまうこと。子が存在しなくてもその位置は確保されるため、2つ目の例の答えは
[1, 2, -1, -1, 3]であり、[1, 2, 3]ではありません。 - 末尾の
-1の要素を残すこと。2^14-1個の要素すべてを返すと、1つ目の例には余分な-1の要素が16376個含まれます。 - 呼び出しのたびに両方の配列のスライスをコピーすること。これでは各レベルで
O(n)の処理が追加されます。インデックス範囲を渡しましょう。 - LuaとRでは、配列のインデックスは1から始まります。計算では位置を0始まりのままにし、
preorder[pre + 1]とout[h + 1]を読み取ります。
よくある質問3
二分木を再構築するために、なぜ先行順と中間順の両方が必要なのですか？
先行順だけでは形は決まりません。先行順の [1, 2] は、2 が 1 の左の子である木にも、右の子である木にも当てはまります。中間順で確定します。[2, 1] なら 2 は左側に、[1, 2] なら右側に配置されます。値がすべて異なる場合、この2つの順序によって木は一意に定まります。
先行順巡回と中間順巡回から二分木を構築する時間計算量はどれくらいですか？
値から中順走査での位置へのマップがあれば、時間計算量は O(n)、追加の空間計算量は O(n) です。マップがない場合、各中順走査の範囲からルートを探す処理に O(n·h) かかり、木がパス状の場合は O(n²) になります。
先行順走査と後行順走査から二分木を再構築できますか？
一般には当てはまりません。先行順走査 [1, 2] と後行順走査 [2, 1] は、左の子にも右の子にも当てはまります。どちらの走査でも、ルートが部分木の間に置かれないためです。この組み合わせだけで十分なのは、すべてのノードが子を0個または2個持つ完全二分木の場合に限られます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def buildTree(preorder, inorder):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
preorder = [7, 3, 0, 9, 4, 6] inorder = [0, 3, 9, 7, 4, 6]
期待される出力
[7, 3, 4, 0, 9, -1, 6]