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]]
- 説明
- ルートの
4には、インデックス1と2に子の9と2があります。インデックス3は空なので、第3レベルには6（インデックス4、9の下）、続いて8と5（インデックス5と6、2の下）があります。インデックス9の3は6の左の子で、第4レベルに単独であります。
- 入力
- 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の要素は何も追加しません。
提出時に隠しテスト+15件
発展問題
各レベルを並べ替えずに、1つ目は左から右へ、2つ目は右から左へ、というようにジグザグ順で返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
インデックス
iの子は2*i+1と2*i+2にあります。常に根に最も近いノードから先に訪れ、その中では左から右へ進むと、ノードに出会う順序はどうなりますか？キューは、ノードを追加した順にノードを取り出します。ノードを取り出すときにその子ノードを追加すると、ノードは一度に1レベルずつ取り出されます。残る課題は、あるレベルの終わりと次のレベルの始まりを示す方法です。
各ラウンドの開始時、キューにはちょうど1つのレベルが入っています。そのサイズ
sを読み取り、s個のノードを取り出して新しいリストに追加し、それらの子を左から追加します。ただし、-1と末尾を越えるインデックスはスキップします。キューが空になったら停止します。
解説
各レベルはそれぞれ独立したリストとして、左から右の順に出力する必要があります。キューを使った幅優先探索では、ノードをまさにその順序で訪問します。追加で必要な考え方は、レベルの終わりを把握することです。各ラウンドの開始時、キューには現在のレベル全体だけが入っているため、そのサイズから処理するノード数がわかります。各ノードの深さを保持し、左から右の順に進むなら、深さ優先探索でも実現できます。
深さ優先、深さごとに整理
考え方
まず、配列内を移動する方法です。インデックス i の左の子は 2i+1 にあり、右の子は 2i+2 にあります。子のインデックスが配列の末尾を超えているか、-1 が格納されている場合、その子は存在しません。例1では、インデックス1の 9 の子はインデックス3と4にあり、そこには -1 と 6 が格納されているので、9 には右の子だけがあります。
次に、深さ優先で木をたどり、各ノードに深さを渡します。根の深さは0です。深さごとにリストを1つ用意します。深さ d のノードに到達したら、その値をリスト d に追加します。リストがまだ d 個しかない場合は、新しいレベルで最初のノードなので、先に新しいリストを作成します。
各レベルのノードが左から右の順に並ぶのはなぜでしょうか。走査では、右部分木に進む前に、あるノードの左部分木全体をたどり終えます。同じレベルにある2つのノードについて考えてみましょう。根からの経路が分岐する箇所で、一方は左へ、もう一方は右へ進みます。走査では左側のノードに先に到達します。例1での順序は 4, 9, 6, 3, 2, 8, 5 で、これによってリストは [4]、[9, 2]、[6, 8, 5]、[3] となります。
各ノードは1回ずつ訪問されるため、ノード数を n とすると、実行時間は O(n) です。また、リストには合計で n 個の値が格納されます。再帰の深さは木の深さまでで、ここでは最大15レベルです。R版では代わりに明示的なスタックを使い、右の子を左の子より先にプッシュすることで、左の子が先に取り出されるようにします。その後、split で値を深さごとにまとめます。
アルゴリズム
- レベルの空のリストを作成します。
- 深さ 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レベル
考え方
キューは、値を追加された順に返します。ルートを入れます。その後、ノードを繰り返し取り出し、その子を入れます。左の子を先に入れます。レベル d の親がキューから出ると、その親のレベル d+1 の各ノードがキューに入るため、レベル d のノードがすべて出てからレベル d+1 のノードが出ます。また、同じレベルのノードは左から右へ出ます。
これにより、レベル順の値の列が得られます。これをレベルごとに分けるには、各ラウンドの開始時にキューのサイズを読み取ります。その時点でキューに入っているのは、現在のレベルのノードだけです。前のレベルのノードはすでに出ており、次のレベルのノードはまだ入っていません。その数だけノードを取り出して、1つのリストにします。それらのノードが追加する子は、次のラウンドに属します。
例1では、キューは [4] から始まります。ノードを1つ取り出して、行は [4] となり、9, 2 が入ります。ノードを2つ取り出して、行は [9, 2] となり、6, 8, 5 が入ります。ノードを3つ取り出して、行は [6, 8, 5] となり、3 が入ります。ノードを1つ取り出して、行は [3] となり、キューは空になります。
各ノードはキューに1回入り、1回出るため、時間計算量は O(n) です。キューに保持されるノード数は最大でもおよそ1レベル分で、深さ14の完全二分木の最深レベルでは16384個です。通常のキューを使うか、先頭位置を示すインデックスを使いましょう。多くの言語では、通常の配列リストから先頭の要素を取り出すと、後続のすべての要素がシフトされます。
アルゴリズム
- 根のインデックス
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を値として扱うこと。空の位置はノードではないため、行にもキューにも入りません。- 範囲チェックを忘れること。最深部のノードの子は配列の末尾を越えた位置にある場合があるため、
tree[child]を読み取る前にchild < nを確認してください。 - 空のレベルを返すこと。末尾の
-1の要素にはノードがないため、[7, -1, -1]に対する答えは[[7]]であり、[[7], []]ではありません。
よくある質問4
二分木のレベル順走査の時間計算量は何ですか？
幅優先と深さ優先のどちらの解法も各ノードを1回ずつ訪問するため、n 個のノードに対して実行時間は O(n) です。答え自体には n 個の値が含まれるため、空間計算量は O(n) です。それに加えて、キューが保持する要素数は最大でも最も幅の広い階層のノード数程度で、再帰の深さは最大でも木の高さです。
幅優先探索では、あるレベルがどこで終わるかをどのように判断しますか？
各ラウンドの開始時にキューのサイズを読み取ります。その時点でキューにはちょうど1つのレベルのノードが入っているため、その数だけノードを取り出せば、そのレベルだけを取り出せます。他にも2つの方法があります。現在のレベルと次のレベルを別々のリストに保持する方法と、各レベルの後にマーカーを追加する方法です。
深さ優先探索でレベル順走査を行うことはできますか？
はい。各ノードに深さを渡し、その深さに対応するリストに値を追加します。左部分木を右部分木より先に訪れる順序で走査すれば、すべてのリストが左から右の順になります。これも O(n) ですが、レベルを順番に生成するため、幅優先探索のほうがより直接的です。
配列はすでにレベルごとに格納されています。スライス単位で読み取ってみてはどうでしょうか？
この形式ではうまくいきます。レベル d はインデックス 2^d-1 から 2^(d+1)-2 を占めるため、各範囲の空でない値を集め、何もない最初の範囲で終了できます。ただし、面接では通常、木は左右のポインターを持つノードオブジェクトとして与えられ、スライスするためのインデックスはありません。キューを使った走査なら、その形式やジグザグ順、右側から見たビューなどの派生形にも応用できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def levelOrder(tree):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
期待値
[[4], [9, 2], [6, 8, 5], [3]]