Maximum Depth of Binary Tree
レベル順に配列 tree に格納された二分木が与えられます。根はインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、配列の末尾には余分な -1 が含まれる場合があります。木の最大の深さ、つまり根から葉までの最長経路上にあるノードの数を返してください。
関数
- treeinteger-array
- 二分木をレベル順に表したもので、空の位置は -1
- 戻り値integer
- 最長の根から葉までの経路上にあるノードの数
制約
1 ≤ tree.length ≤ 32767- 各
tree[i]は-1、または0 ≤ tree[i] ≤ 1000を満たす値です。 tree[0]は決して-1ではないため、木には少なくとも1つのノードがあります。- 配列は最後のノードの後に余分な
-1のエントリが続く場合があります。 - 空の位置の子も両方とも空で、深さは最大でも
14です。
例
- 入力
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- 出力
- 4
- 説明
- 最長のパスは
5、8、3、6（インデックス0、1、4、9）で、4 個のノードがあります。1を通るパスは2個のノードの後で止まります。
- 入力
- tree = [7, -1, -1]
- 出力
- 1
- 説明
- 2つの
-1エントリは、ルートの空の子ノード位置です。ルートだけでも1ノードのパスなので、深さは0ではなく1です。
- 入力
- tree = [2, -1, 9, -1, -1, -1, 4]
- 出力
- 3
- 説明
- ルート
2には左の子がありません。インデックス2にある右の子9は、インデックス6にある4を右の子として持ち、3ノードの経路を形成します。
発展問題
最長の根から葉への経路上の値と、その長さをどのように返しますか？複数の経路が同じ長さの場合、どの経路を返しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ルートについて考えてみましょう。左部分木の深さと右部分木の深さがわかっているとしたら、木全体の深さはいくつになるでしょうか？
根の分として
1を加え、2つの部分木の深さの大きい方を足します。空の位置の深さは0です。同じ規則がすべてのノードに当てはまるため、各ノードの深さがわかる走査によって答えを求められます。ペアのスタックを保持します。ペアにはノードのインデックスと深さを格納し、ルートの深さを1として開始します。ペアを取り出し、これまでに見た最大の深さを記録します。配列内にあり、
-1ではない各子を、深さに1を加えて2*i+1および2*i+2にプッシュします。
解説
深さは最も長い枝によって決まり、すべてのノードを訪問しないと、どの枝が最も長いかはわかりません。そのため、各ノードでの深さを把握しながら、全体を一度走査する必要があります。再帰、レベルごとの幅優先探索、自分で用意したスタックを使う深さ優先探索なら、いずれも1回の走査で実行できます。
2つの部分木に対する再帰
考え方
子の位置が実在するのは、そのインデックスが配列の範囲内にあり、その値が -1 ではない場合です。ノードを通る最も深い経路は、そのノードのより深い部分木へと進むため、インデックス i における深さは、ノード自身の分の 1 に、2*i+1 と 2*i+2 における深さの大きい方を加えた値になります。空の位置の深さは 0 で、これによって再帰が終了します。葉の深さは 1 + max(0, 0) = 1 となり、値は根に向かって積み上がっていきます。
各ノードは 1 回ずつ訪問されます。呼び出しスタックには現在の経路のレベルごとに 1 つのフレームが保持され、O(h) となります。ここでは最大 14 です。
アルゴリズム
depth(i)を作成します。iが配列の末尾を超えている場合、またはtree[i]が-1の場合は、0を返します。- それ以外の場合は、
1 + max(depth(2*i+1), depth(2*i+2))を返します。 depth(0)を返します。
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)幅優先探索、レベルごとに
考え方
最大深さは階層の数なので、経路をたどる代わりに階層を数えられます。キューはノードを階層順に訪問します。各バッチの前にキューのサイズを確認します。バッチ中に追加する子ノードはそれらの後ろに入るため、そのノードがちょうど1つの階層を構成します。各バッチで深さに1を加えます。最初の例では、バッチは [5]、[8, 1]、[3]、[6] なので、答えは4です。
キューに保持されるのは一度に1つの階層で、最も幅の広い階層の場合で O(w) です。深さ14の完全二分木では、16383個のノードのうち8192個です。
アルゴリズム
- ルートのインデックス
0をキューに入れ、depth = 0に設定します。 - キューが空でない間、
depthに1を加算し、キューのサイズを読み取ります。 - その数だけインデックスを取り出します。それぞれについて、配列内にあり
-1ではない子のインデックス2*i+1と2*i+2をキューに入れます。 - キューが空になったら、
depthを返します。
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depth明示的なスタックを使用した深さ優先探索
考え方
ノードの深さを覚えておくものはほかにないので、ノードのインデックスとその深さのペアを自分でスタックに保持します。(0, 1)、つまり深さ1のルートから始めます。各ノードは、そのノードに至る経路の長さを持って一度だけプッシュされるため、ポップしたときの最大の深さが答えになります。最初の例では、6は(9, 4)としてプッシュされます。
スタックが保持するのは各レベルにつき、およそ保留中の兄弟ノード1つ分で、O(h)です。呼び出しスタックがあふれることもありません。同じコードは、深さを問わずポインタベースの木で動作します。
アルゴリズム
(0, 1)をスタックにプッシュし、best = 0を設定します。- ペア
(i, depth)をポップし、bestとdepthの大きい方をbestに設定します。 - 配列内にあり、
-1ではない各子インデックス2*i+1と2*i+2について、depth + 1とともにプッシュします。 - スタックが空になるまで繰り返し、その後
bestを返します。
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
落とし穴と境界ケース
- ノードではなく辺を数える。
[7, -1, -1]の深さは0ではなく1。 - 範囲チェックを省略する。最初の例では、インデックス9の
6の子インデックスは19と20で、配列の末尾を超えている。tree[child]を読み取る前にchild < nを確認する。 - 配列の長さから深さを計算する。末尾の
-1の要素は、ノードのないレベルに達する。[7, -1, -1]の長さは3だが、深さは1。 - バッチループ内でキューのサイズを読み取る。バッチ処理中に追加された子によってサイズが変わるため、先に保存する。
- 配列が1から始まるLuaとRで、オフセットを取り違える。ノードインデックスは
2*i+1のために0ベースのままにし、tree[i + 1]を読み取る。
よくある質問3
二分木の最大深さの時間計算量はどれくらいですか？
どの方法でも各ノードを1回ずつ訪れるため、時間計算量はO(n)です。深さ優先の方法では、現在の経路のためにO(h)の追加領域を使います。ここで、hは深さです。幅優先の方法では、最も幅の広いレベルのためにO(w)を使います。完全二分木では、これはノード数のおよそ半分です。
二分木の最大深さを求めるには、DFSとBFSのどちらを使うべきですか？
どちらもO(n)時間で実行されます。深さ優先探索は記述が短く、深さに比例したメモリを使用するため、幅が広く浅い木に適しています。幅優先探索はレベルを直接数え、最も幅の広いレベルに比例したメモリを使用するため、深く狭い木に適しています。最小の深さを求める場合は、最初の葉で探索を終了できるため、幅優先探索が有利です。
二分木の深さと高さの違いは何ですか？
ノードの深さは、ルートからそのノードまで下りるステップ数を数えます。高さは、そのノードから最も深い葉まで下りるステップ数を数えます。木の最大深さはルートの高さと等しくなります。この問題ではノード数を数えるため、ノードが1つだけの場合の深さは1です。辺を数える場合は1少なくなります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def maxDepth(tree):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
期待される出力
4