Binary Tree Level Order Traversal
配列 tree には二分木が格納されています。ルートはインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、末尾に余分な -1 の要素が続く場合があります。
ノードの値をレベルごとに返してください。ルートから最も深いレベルまで、各レベルにつき1つのリストとし、それぞれの値は左から右の順に並べます。
関数
- treeinteger-array
- ヒープ順序で表した木（空の位置は -1）
- 戻り値integer-2d-array
- 各レベルにつき値のリストを1つ。最上位レベルから順に、それぞれ左から右へ
制約
1 ≤ tree.length ≤ 32767- 各
tree[i]は-1または0 ≤ tree[i] ≤ 1000を満たす値です。 tree[0]は決して-1ではないため、ツリーには少なくとも 1 つのノードがあります。- 配列の末尾には、最後のノードより後に余分な
-1のエントリが含まれる場合があります。 - 空のスポットの子も両方とも空で、深さは最大でも
14です。
例
- 入力
- tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
- 出力
- [[4], [9, 2], [6, 8, 5], [3]]
- 説明
- インデックス3は空なので、
9には右の子である6だけがあります。第3レベルは6、8、5で、第4レベルでは6の下にあるインデックス9の3だけです。
- 入力
- tree = [7, -1, -1]
- 出力
- [[7]]
- 説明
- ルートの子は両方とも
-1なので、木は単一のノード7であり、レベルは1つです。
- 入力
- tree = [1, 3, -1, 5, -1, -1, -1]
- 出力
- [[1], [3], [5]]
- 説明
- 各ノードには左の子のみがあります。インデックス1の
3とインデックス3の5です。各レベルには値が1つあり、末尾の-1の要素は何も追加しません。
発展問題
各レベルを並べ替えずに、最初は左から右へ、2番目は右から左へ、というようにジグザグ順で返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
インデックス
iの子は2*i+1と2*i+2にあります。常に根に最も近いノードから先に訪れ、それらの間を左から右へ進むと、ノードにはどのような順序で出会いますか？キューは、ノードを入れた順に取り出します。ノードを取り出すときにその子ノードを追加すると、ノードは一度に1つのレベルずつ取り出されます。残っているのは、あるレベルがどこで終わり、次のレベルがどこで始まるかを示すことです。
各ラウンドの開始時に、キューにはちょうど1つのレベルが入っています。そのサイズ
sを読み取り、s個のノードを取り出して新しいリストに入れ、それらの子を左側から追加します。-1と末尾を超えるインデックスはスキップします。キューが空になったら停止します。
解説
各レベルは、それぞれ左から右へのリストとして出力する必要があります。キューを使った幅優先探索ではノードがその順序で訪問され、各ラウンドの開始時にはキューにちょうど1つのレベルのノードが入っているため、キューのサイズから取り出すノードの数がわかります。各ノードの深さを記録する深さ優先探索でも同じことができます。
深さ優先、深さ順に記録
考え方
木を深さ優先でたどり、各ノードに深さ（ルートは0）を渡し、深さごとに1つのリストを保持します。深さ d のノードは、その値をリスト d に追加します。そのレベルで最初に見つかったノードであれば、そのリストを作成します。
各リストは左から右の順になります。これは、右の部分木に入る前に、ノードの左の部分木を最後までたどるためです。同じレベルにある2つのノードのうち、経路が分岐する場所で左に曲がる経路上のノードが先に訪問されます。例1では、訪問順 4, 9, 6, 3, 2, 8, 5 によって、[4]、[9, 2]、[6, 8, 5]、[3] が作られます。
各ノードは1回ずつ訪問されます。時間計算量は O(n) で、再帰の深さは木と同じ深さとなり、最大14レベルです。
アルゴリズム
- レベルの空のリストを作成します。
- 深さ0でルートを訪問します。
- 深さ
dのノードiで、iが末尾を過ぎているか、tree[i]が-1の場合は停止します。 d個のリストしかない場合は、空のリストを追加します。tree[i]をリストdに追加します。- 深さ
d+1で、まず2i+1を、次に2i+2を訪問します。
def levelOrder(tree):
n = len(tree)
levels = []
def visit(i, depth):
if i >= n or tree[i] == -1:
return
if depth == len(levels): # the first node seen on this level
levels.append([])
levels[depth].append(tree[i])
# Left before right, so every level fills from left to right.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return levels幅優先探索、1ラウンドにつき1レベル
考え方
キューからノードを取り出し、その子ノードを左から順に入れます。レベル d+1 はレベル d が出ていくときにのみ入るため、ノードはレベルごとに左から右へ出ていきます。
この流れをレベルごとに区切るには、各ラウンドの開始時にキューのサイズを読み取ります。前のレベルはなくなっており、次のレベルのノードはまだ入っていないため、キューには現在のレベルのノードだけが入っています。その数だけノードを取り出して1つの行にまとめます。子ノードは次のラウンドまで待ちます。例1では、各ラウンドで1、2、3、1個のノードを取り出します。
すべてのノードはキューに1回入り、1回出ます。時間計算量は O(n) です。キューが保持するのはおよそ1レベル分で、14レベルの完全な木の最深レベルでは最大8,192個のノードです。
アルゴリズム
- ルートのインデックス
0をキューに入れます。 - キューが空でない間、そのサイズ
sを読み取り、空の行を開始します。 s個のインデックスを取り出します。各インデックスiについて、tree[i]を行に追加します。- インデックスが配列の範囲内にあり、
-1が格納されていない場合、2i+1、次に2i+2をキューに追加します。 - その行を答えに追加し、次のラウンドを開始します。
from collections import deque
def levelOrder(tree):
n = len(tree)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(tree[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
levels.append(row)
return levels
落とし穴と境界ケース
- キューを空にしている間に、そのサイズを読み取ること。
while (j < queue.length)では、子ノードが追加されるにつれて長さが増えるため、次のレベルのノードが現在の行に混ざってしまいます。 - 右の子を左の子より先に追加する、または右部分木を先に訪問すること。そうすると、例1の第2レベルは
[2, 9]になります。 - 境界チェック
child < nを省略すること。最も深いノードの子は、配列の末尾を超えた位置にあります。 - 通常の配列リストの先頭から要素を削除すること。多くの言語では、そのたびにキュー全体がシフトされます。実際のキューか、先頭位置を示すインデックスを使いましょう。
-1をノードとして扱うこと。これは行にもキューにも入りません。[7, -1, -1]から得られるのは[[7]]であり、[[7], []]ではありません。
よくある質問3
二分木のレベル順走査の時間計算量はどれくらいですか？
どちらの解法も各ノードを1回ずつ訪問します。n 個のノードに対して時間計算量は O(n) です。答えには n 個の値が格納されるため、空間計算量は O(n) です。それに加えて、キューには最も幅の広いレベルのノード数程度が格納され、再帰には木の高さ分のスタック領域が必要です。
幅優先探索では、あるレベルがどこで終わるかをどのように判断しますか？
各ラウンドの開始時にキューのサイズを読み取り、その数だけノードを取り出します。他にも2つの方法があります。現在のレベルと次のレベルを別々のリストに保持するか、各レベルの後にマーカーをキューに追加します。
配列はすでにレベルごとに格納されています。スライス単位で読み取ってみてはどうでしょうか？
この形式では、根を0とするレベルdはインデックス2^d-1から2^(d+1)-2までを埋めるため、範囲に値がなくなるまで各範囲の空でない値を集めます。面接では通常、代わりにポインターを持つノードオブジェクトが渡されますが、その形式でも引き継がれるのはキューだけです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def levelOrder(tree):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
期待される出力
[[4], [9, 2], [6, 8, 5], [3]]