Binary Tree Right Side View
配列 root には二分木が格納されています。ルートはインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、末尾に余分な -1 が続く場合があります。
木を右側から見てください。各レベルでは、最も右にあるノードだけが見え、残りは隠れます。ルートのレベルから最も深いレベルまで、その値を列挙してください。
関数
- rootinteger-array
- ヒープ順序の木で、空の位置には -1 を使用
- 戻り値integer-array
- 各レベルの最も右の値（最上位レベルから順に）
制約
1 ≤ root.length ≤ 32767- 各
root[i]は-1、または0 ≤ root[i] ≤ 104を満たす値です。 - ノードの値はそれぞれ異なります。
root[0]が-1になることは決してないため、ツリーには少なくとも1つのノードがあります。- 配列は、最後のノードより後ろに余分な
-1のエントリが続くことがあります。 - 空の場所の子は両方とも空で、木のレベル数は最大でも
14です。
例
- 入力
- root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
- 出力
- [5, 9, 1, 3]
- 説明
- 右側からは
5、9、1（インデックス6）が見えます。第4レベルには、左部分木の7の下、インデックス8にある3だけがあります。右側にはそこまで深い位置にあるものはないため、3が見えます。
- 入力
- root = [6, 0, -1, 8, -1, -1, -1]
- 出力
- [6, 0, 8]
- 説明
- この木は左の子が連なる構造です：
6、0、8。各レベルにはノードが1つずつあるため、右の子ではないにもかかわらず、3つすべてが表示されます。
- 入力
- root = [42]
- 出力
- [42]
- 説明
- 長さ1の配列です。ルートの
42には子の場所がまったくなく、ビューはその1つの値です。
発展問題
すべてのノードが任意の数の子を持つことができ、それらが左から右へのリストとして格納されている木の右側面図を、どのように取得しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
例1の右の子をたどると、
5, 9, 1となり、そこで止まります。答えには4つ目の値があります。それはどこから来るのでしょうか？ノードを左右ではなく深さごとにグループ化します。各レベルを左から右へ書き出します。そのリストの中で、右側にいる人から見えるノードはどれですか？
viewというリストを保持します。深さを指定して深さ優先で探索し、右の子を左の子より先に訪問します。ノードの深さがviewの長さと等しいとき、そのノードを追加します。キューを使い、各ラウンドで1レベルずつ処理する方法でもかまいません。その場合は各ラウンドの最後のノードを追加します。
解説
各レベルの最も右にあるノードを確認します。必ずしも右の子ノードとは限りません。例1の最後の値は左部分木にあります。幅優先探索では、そのノードは各ラウンドの最後に訪問されます。右から先に進む深さ優先探索では、同じレベルのほかのどのノードよりも先にそのノードに到達します。
幅優先探索、各レベルの最後のノード
考え方
木を1ラウンドにつき1レベルずつ処理します。ラウンドが始まると、キューには左から右へちょうど1レベル分のノードが入っているため、そのラウンドでデキューする最後のインデックスがそのレベルの最も右にあるノードになり、その値を答えに追加します。
例1では、ラウンドは [5]、[2, 9]、[7, 4, 1]、[3] で、各ラウンドの最後の要素から 5, 9, 1, 3 が得られます。決め手となるのは左右どちら側かではなく、レベルです。3 は左部分木にありますが、そのレベルには単独で存在します。
各インデックスは1回ずつエンキューおよびデキューされるため、時間計算量は O(n) です。キューのサイズは最も幅の広いレベルまで増え、最悪の場合は O(n) になります。
アルゴリズム
- ルートのインデックス
0をキューに追加します。 - キューの長さ
sを保存して、ラウンドを開始します。 s個のインデックスをデキューします。各インデックスiについて、配列の長さ未満であり、かつ-1ではない場合、2i+1を追加し、その後2i+2を追加します。- そのラウンドで最後にデキューしたインデックスの値を追加します。
- キューが空になるまで繰り返し、その後答えを返します。
from collections import deque
def rightSideView(root):
n = len(root)
view = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
size = len(queue) # exactly the nodes of the current level
for j in range(size):
i = queue.popleft()
if j == size - 1:
view.append(root[i]) # the last node of this level
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
return view深さ優先、右の子を先に
考え方
深さ優先で探索し、左の子より先に右の子を試し、根の深さを 0 として深さを保持します。探索が初めて深さ d に到達したとき、答えにはちょうど d 個の値が入っています。そのときノードの値を追加し、そのレベルにある後続のノードはすべて無視します。
その最初のノードが最も右にあるノードです。レベルへの2つの経路が分かれる場所では、探索は左の経路に戻る前に右の枝を末端までたどります。例1では、探索は 5, 9, 1, 2, 4, 7, 3 の順にノードを訪れます。深さにすでに値がある 2、4、7 は飛ばし、3 を追加します。
各ノードを1回ずつ訪れるため、時間計算量は O(n) で、スタック上の呼び出しは各レベルにつき1つ、最大でも14です。
アルゴリズム
- 空の answer から始め、ルートの深さを 0 とします。
- 配列の末尾を越えているインデックス、または
-1を保持しているインデックスはスキップします。 - answer の長さが深さと等しい場合、値を追加します。走査が新しいレベルに到達し、右側から到達したことになります。
- まず右の子
2i+2に再帰し、次に左の子2i+1に再帰します。それぞれ深さを 1 増やします。 - answer を返します。
def rightSideView(root):
n = len(root)
view = []
def visit(i, depth):
if i >= n or root[i] == -1:
return
if depth == len(view): # the first node met on this level
view.append(root[i])
# Right before left, so the rightmost node of every level comes first.
visit(2 * i + 2, depth + 1)
visit(2 * i + 1, depth + 1)
visit(0, 0)
return view
落とし穴と境界ケース
- ルートから右の子だけをたどる。例1では
[5, 9, 1]となり、3を見落とす。例2では[6]となる。 - 各レベルの最後のスロット
root[2^(d+1)-2]を読み取る。例2ではインデックス6に-1が入っている。見えるノードはインデックス3の8である。 - 子の位置の長さチェックを省略する。例1では
3が最後の要素なので、その子の位置17と18は存在しない。 - 各ラウンドの最後のノードを保持しながら、右の子を先にキューに入れる。これでは左側面
[5, 2, 7, 3]が集められる。 - 右からたどる際に後のノードで前のノードを上書きする。これでも左側面が得られる。
よくある質問3
二分木の右側面図の時間計算量と空間計算量はどのくらいですか？
時間計算量は O(n) 個のノードに対して O(n) であり、ノードをスキップできる解法はありません。あるレベルの右端のノードは、どこにでも位置する可能性があるためです。キューを使う場合、空間計算量は w が最も幅の広いレベルの幅であるとき O(w) です。また、h レベルの木を右優先でたどる場合は O(h) です。
左優先の深さ優先探索で解けますか？
はい、最初の値を保持せずに上書きするなら可能です。左優先の走査では、各レベルのノードに左から右へ順に出会うため、各深さで各ノードの値を保存し、後続のノードで先行する値を置き換えます。各深さには、最後にその深さで最も右にある値が残ります。計算量は依然として O(n) ですが、ノードごとに1回書き込みます。
ここでは幅優先探索と深さ優先探索のどちらを使うべきですか？
どちらも線形です。幅優先探索は定義どおりに、1ラウンドにつき1つのレベルを進みます。深さ優先探索は現在の経路だけを保持するため、幅の広い木ではメモリを節約でき、再帰形式なら数行短くなります。
def rightSideView(root):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
期待される出力
[5, 9, 1, 3]