Left View of Binary Tree
ヒープ順序の配列 root として二分木が与えられます。ルートはインデックス 0 にあり、インデックス i の子は 2*i+1（左）と 2*i+2（右）にあります。また、-1 は空の位置を示します。配列の末尾に余分な -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 = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
- 出力
- [3, 8, 6, 1]
- 説明
8は葉なので、第3レベルと第4レベルには、右の子5の下にある6（インデックス 6）と1（インデックス 13）だけがあります。それでも、これらは見えています:[3, 8, 6, 1]。
- 入力
- root = [10, -1, -1]
- 出力
- [10]
- 説明
- インデックス 1 と 2 には
-1が格納されているため、10には子がなく、ビューにはルートのみが表示されます。
- 入力
- root = [1, 2, 3, 4, 5, 6, 7]
- 出力
- [1, 2, 4]
- 説明
- 3 階層の完全な木です。各階層の最も左の位置のインデックスは 0、1、3 で、それぞれ
1、2、4を保持します。
発展問題
レベル d は、インデックス 2^d-1 から 2^(d+1)-2 までを埋めます。キューも再帰も使わず、それらの範囲を走査してビューを構築できますか？パディングされた配列では、コストはどうなりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
あるレベルに見えるノードが、常に左の子とは限りません。例1では、3番目のレベルに見えるノードはどれで、誰の子ですか？
ノードをレベルごとにグループ化します。各レベルを左から右へたどると、目的のノードはそのレベルで最初に出会うノードです。
キューを1ラウンドにつき1レベルずつ処理し、各ラウンドの最初のノードを保持します。または、深さ優先でたどり、深さを引き継ぎ、右より先に左へ進み、ノードの深さが記録済みの値の数と等しいときにそのノードを記録します。
解説
根から左の子をたどる方法では、左部分木のほうが短い場合にうまくいきません。最初の例では、下の階層が右部分木を通して見えることになります。各階層の最初のノードが必要です。幅優先探索では各階層を左から右へ順にたどり、左を優先する深さ優先探索では、各階層の最も左にあるノードに最初に到達します。
幅優先探索、各レベルの最初のノード
考え方
キューをラウンドごとに処理すると、レベルが一度に1つずつ得られます。ラウンドの開始時、キューには左から右の順にレベルがちょうど1つ格納されています。ラウンド中に追加される子ノードはすべてその後ろに入るためです。その数だけインデックスを取り出し、それぞれの子ノードを左からキューに追加して、最初の値を保持します。
最初の例では、ラウンドは [3]、[8, 5]、[6]、[1] となり、それぞれ3、8、6、1を保持します。子ノードの位置3と4には -1 が入っているため、8 は何も追加しません。
各ノードはキューに一度入り、一度出ます。時間計算量は O(n) です。キューにはレベル全体が格納され、14レベルの完全な木では最大8192個のインデックスを保持します。
アルゴリズム
- インデックス
0を保持するキューと、空の答えを用意します。 - キューが空でない間、
sをそのサイズとし、インデックスをs個取り出します。最初のインデックスの値を追加します。 - 取り出した各インデックス
iについて、末尾を超えるインデックスと値が-1の要素をスキップしながら、2i+1、次に2i+2をキューに追加します。
from collections import deque
def leftView(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 == 0:
view.append(root[i]) # the first 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深さ優先、左の子を先に
考え方
深さ優先で、左部分木を右部分木より先にたどり、各ノードの深さを渡します。探索で深さ d に到達する最初のノードが、レベル d の最も左のノードです。あるレベルで最も左のノード x と、その右にある任意のノード y を考えます。両者の経路が最後に共有するノードで、x は左に進み、y は右に進みます。そして探索は、右に進む前に左の枝を最後までたどります。
探索は一度に1レベルずつ下るため、深さ d に初めて到達したとき、答えにはちょうど d 個の値が入っています。d が答えの長さと等しいときにノードを記録すればよく、訪問済みの深さを記録する集合は必要ありません。
各ノードは1回ずつ訪問され、時間計算量は O(n) です。メモリには各レベルにつき1回分の呼び出しが保持され、ここでは最大14です。R版は独自のスタックを保持し、左の子より先に右の子をプッシュします。
アルゴリズム
- 空の答えを作成し、
visit(0, 0)を呼び出します。 visit(i, d)では、iが配列の範囲外にある場合、またはroot[i]が-1の場合は、ただちに戻ります。dが答えの長さと等しい場合、探索は初めてレベルdに到達しています。root[i]を追加します。visit(2i+1, d+1)を呼び出し、次にvisit(2i+2, d+1)を呼び出します。- 最初の呼び出しが完了したら、答えを返します。
def leftView(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])
# Left before right, so the leftmost node of every level comes first.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return view
落とし穴と境界ケース
- ルートから左の子だけをたどる。最初の例では
8で止まり、6と1を見落とします。 - 各レベルの最初のスロット
root[2^d-1]を読む。最初の例では、3番目のレベルの最初のスロット（インデックス3）には-1が格納されていますが、そのレベルにある唯一のノードはインデックス6にあります。 - 深さ優先探索で右の子を先に訪問する。すると、各レベルで最初に見つかるノードは最も右にあるノードになります。
- 境界チェックなしで子を読み取る。インデックス13の
1には、14個の要素を持つ配列の末尾を越えたインデックス27と28に子の位置があります。
よくある質問3
左側のビューは、木の左境界と同じですか？
いいえ。左境界はパスです。ルートの左の子から始まり、左に進める場合は左へ、そうでなければ右へ進み、葉の手前で止まります。左側ビューでは、どの枝からでも各レベルにつき1つのノードを選びます。最初の例では、8は葉なので境界は空ですが、ビューには8、6、1が表示されます。
左側から見たビューの時間計算量と空間計算量はどのくらいですか？
どちらの解法も各ノードを1回ずつ調べるため、時間計算量は O(n) です。幅優先探索のキューには1つのレベル全体が格納され、完全二分木ではノードの約半数に相当します。左から優先する探索では、各レベルにつき1つの呼び出しが保持され、h レベルの場合は O(h) です。
正しいビューを得るには、解決策をどのように変更すればよいですか？
幅優先版では、各ラウンドの最初の値ではなく最後の値を保持します。深さ優先版では、左の子より先に右の子を訪問します。そうすると、各レベルで探索が最初に到達するノードが右端になります。
def leftView(root):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
期待される出力
[3, 8, 6, 1]