Vertical Order Traversal of a Binary Tree
二分木は、ヒープ順で配列 root に格納されています。ルートはインデックス 0 にあり、インデックス i の子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、配列の末尾に余分な -1 が含まれる場合があります。
ルートは列 0 にあります。左の子は親より1列左、右の子は親より1列右です。左から右へ、列ごとに1つのリストを返してください。各列ではノードを上から下へ並べ、同じ列かつ同じ深さのノードは値の昇順で並べてください。
関数
- rootinteger-array
- ヒープ順序の木（空の位置は -1）
- 戻り値integer-2d-array
- 列ごとに値のリストを1つずつ、左端の列から順に、それぞれ上から下へ
制約
1 ≤ root.length ≤ 32767- 各
root[i]は-1、または0 ≤ root[i] ≤ 5000を満たす値であり、同じ値が2回以上現れることはありません。 root[0]は決して-1ではないため、木には少なくとも1つのノードがあります。- 配列の末尾には、最後のノードより後に余分な
-1の要素が入っている場合があります。 - 空の位置の子は両方とも空であり、木のレベル数は最大で
14です。
例
- 入力
- root = [5, 2, 9, 4, 7, 1, 6]
- 出力
- [[4], [2], [5, 1, 7], [9], [6]]
- 説明
- 列0にはルートの
5があり、その2階層下に7と1があります。この2つは列と深さが同じなので、7のほうが左にあるにもかかわらず、1が先に来ます。
- 入力
- root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
- 出力
- [[2, 5], [1, 4], [3]]
- 説明
- 列 -1 には深さ 1 の
2と、深さ 3 の5（4の左の子）が入ります。列 0 にはルートの1と、インデックス 4 の4が入ります。列 1 には3だけが入ります。
- 入力
- root = [6, -1, -1]
- 出力
- [[6]]
- 説明
6には子がないため、答えは1列の[6]になります。
発展問題
すべての値は最大でも5000です。この性質を利用して比較ソートを使わずに、O(n + 5000)時間で処理を終えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべてのノードには、列、深さ、値があります。これらの3つ組をすべて1つのリストにまとめた場合、どのような順序で答えに並べますか？
幅優先探索では、ノードがすでに上から下へと並びます。同じ列とレベルに複数のノードがある場合、順序のどの部分がまだ決まっていないのでしょうか？
木を一度に1つのレベルずつ処理します。各レベルを列、次に値の順に並べ替え、各値を対応する列のリストに追加し、最後に最も小さい列から最も大きい列へとリストを読み取ります。
解説
各ノードには、column、depth、valueという3つのキーがあります。答えは、これらのキーで並べ替えたノードを、列ごとに1つのリストにまとめたものです。columnとdepthが同じ場合は、走査で出会う左から右の順ではなくvalueで順序が決まるため、すべてのノードを一度に、または幅優先探索の各レベルごとに並べ替える必要があります。
すべてのノードを記録してから、並べ替える
考え方
順序は問わず各ノードを1回ずつ訪問し、3つ組（列、深さ、値）を記録します。子ノードへ進むと深さが1増え、列が左右どちらかに1つ移動します。次に、3つ組を列、深さ、値の順に並べ替えます。これで各列のノードが必要な順序でまとまります。並べ替えたリストをたどり、列が変わるたびに新しい内側のリストを開始します。
例1では、列0の3つ組は (0, 0, 5)、(0, 2, 1)、(0, 2, 7) の順に並びます。O(n log n) の並べ替えが O(n) の走査より支配的で、3つ組は O(n) の領域を使用します。
アルゴリズム
- スタックに (インデックス 0、列 0、深さ 0) をプッシュします。
- ノードをポップし、(列、深さ、値) を記録して、各実在する子を列
col-1またはcol+1、深さdepth+1でプッシュします。 - スタックが空になったら、列、次に深さ、次に値の順にタプルをソートします。
- 列が変わるたびに新しいリストを開始しながら、それらをたどります。
def verticalTraversal(root):
n = len(root)
entries = [] # (column, depth, value) for every node
stack = [(0, 0, 0)] # (node index, column, depth); the root is never empty
while stack:
i, col, depth = stack.pop()
entries.append((col, depth, root[i]))
for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
if child < n and root[child] != -1:
stack.append((child, child_col, depth + 1))
# Column, then depth, then value: exactly the order of the answer.
entries.sort()
result = []
for k, (col, depth, value) in enumerate(entries):
if k == 0 or col != entries[k - 1][0]:
result.append([]) # a new column starts
result[-1].append(value)
return result各レベル内で、レベルごとに並べ替える
考え方
幅優先探索では、一度に1つのレベルを処理します。各ノードを処理するときにその値を列のリストに追加すれば、各リストはすでに上から下の順になっているため、深さで並べ替える必要はありません。同順位になるのは同じレベル内だけなので、処理する前に各レベルを列、次に値の順で並べ替えます。
例1では、レベル2のノードは列 -2、0、0、2 の順に 4, 7, 1, 6 として到着し、並べ替えると 4, 1, 7, 6 になります。そのため、列0は [5, 1, 7] となります。列は途切れのない範囲を形成するので、最小値と最大値を記録するだけで十分です。
m 個のノードがあるレベルの並べ替えには O(m log m) のコストがかかります。完全二分木の最後のレベルにはノードの約半数が含まれるため、最悪の場合でも O(n log n) です。空間計算量は O(n) です。
アルゴリズム
- レベル（インデックス 0、列 0）を保持することから始めます。
- レベルを列、次に値の順に並べ替えます。
- その順序で各値を対応する列のリストに追加し、実際の子要素を列
col-1とcol+1とともに次のレベルに集めます。 - レベルが空になるまで繰り返し、最小列と最大列を追跡します。
- 最小列から最大列までのリストを返します。
def verticalTraversal(root):
n = len(root)
columns = {} # column -> its values, top to bottom
level = [(0, 0)] # (node index, column) of every node on the current level
while level:
# Every node here has the same depth: order them by column, then value.
level.sort(key=lambda node: (node[1], root[node[0]]))
next_level = []
for i, col in level:
columns.setdefault(col, []).append(root[i])
for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
if child < n and root[child] != -1:
next_level.append((child, child_col))
level = next_level
# The columns that hold a node form one unbroken range.
return [columns[col] for col in range(min(columns), max(columns) + 1)]
落とし穴と境界ケース
- 同じ位置の場合に左から右の順序を維持すること。レベルごとにソートしない幅優先探索では、例1の列0は
[5, 1, 7]ではなく[5, 7, 1]になります。 - ソートせずに深さ優先探索中に値を追加すること。
[1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5]では、左から先に進む探索は3（深さ1）より先に5（深さ3）を列1に追加します。 - 列と値でソートし、深さでソートしないこと。その場合、例1の列0は
[1, 5, 7]になります。 - 列を文字列でキー付けすること。テキストとしてソートすると、
"-1"は"-2"より前になるため、0より左の列の順序が誤ったものになります。
よくある質問3
二分木の垂直順序トラバーサルの時間計算量はどれくらいですか？
すべてのノードを列、深さ、値でソートするには O(n log n) のコストがかかり、O(n) の走査よりも時間がかかります。レベルごとにソートする場合も最悪計算量は同じです。完全二分木では、最終レベルにノードのおよそ半数が含まれるためです。空間計算量は O(n) です。
垂直順序トラバーサルはソートせずに実行できますか？
同順位が左から右の順になる場合に限ります。その場合、各値をその列のリストに追加する幅優先探索で、O(n)で答えを求められます。同順位を値で並べる場合は、並べ替えが必要ですが、同順位になるのは同じレベルのノードだけなので、レベル内だけで十分です。
垂直順序走査は、上面図や下面図とどのように関係していますか？
3つすべてのグループ化では、同じ列番号でノードをまとめます。上面図では各列の最も浅いノードを、下面図では最も深いノードを保持します。垂直順序トラバーサルではすべてのノードを保持し、同じレベルに複数のノードがある場合は値で並べ替えますが、各ビューでは位置に基づいて選択します。
def verticalTraversal(root):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
root = [5, 2, 9, 4, 7, 1, 6]
期待される出力
[[4], [2], [5, 1, 7], [9], [6]]