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 ノードの経路になります。
提出時に隠しテスト+13件
発展問題
最長の根から葉までの経路の長さだけでなく、その経路上の値を返すにはどうすればよいでしょうか。複数の経路が同じ長さの場合、どの経路を返しますか。また、そのことを契約でどのように明記しますか。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ルートについて考えてみましょう。左部分木の深さと右部分木の深さが分かっていたら、木全体の深さはどうなるでしょうか？
これは、根の分としての
1に2つの部分木の深さの大きい方を加えた値で、空の位置の深さは0です。同じ規則がすべてのノードに当てはまるため、各ノードの深さがわかる走査によって答えを求められます。- 深さ1のルートから始め、ノードのインデックスとその深さのペアをスタックに保持します。ペアを取り出し、これまでに見た最大の深さを記録します。配列の範囲内にあり、
-1ではない各子ノードを、深さを1増やして2*i+1と2*i+2にプッシュします。
解説
深さは最も長い枝によって決まり、すべてのノードを調べなければ、どの枝が最も長いかはわかりません。そのため、各ノードでどの深さにいるかを把握しながら、すべてを走査する必要があります。再帰、レベルごとの幅優先探索、自分でスタックを用意する深さ優先探索は、いずれも1回の走査でこれを実現できます。それぞれ、現在の位置を把握する方法が異なります。
2つの部分木での再帰
考え方
まず、配列内の移動方法を見ていきましょう。インデックス i のノードの左の子は 2*i+1 に、右の子は 2*i+2 にあります。子が実際に存在するのは、そのインデックスが配列の範囲内にあり、そこにある値が -1 ではない場合だけです。[5, 8, 1, -1, 3, -1, -1, -1, -1, 6] では、根 5 の子はインデックス 1 と 2 にあります。インデックス 1 の 8 は、左側の 3 に空きがあり、右側のインデックス 4 に 3 があります。そして、その 3 の下にはインデックス 9 の 6 があります。
では、考え方を見ていきましょう。あるノードを通る最も深い経路は、2つの部分木のうち、より深いほうへ進みます。したがって、インデックス i の部分木の深さは、そのノード自体の 1 に、2*i+1 と 2*i+2 の位置にある部分木の深さの大きいほうを足したものです。空の位置の深さは 0 で、ここで再帰が終了します。葉の深さは 1 + max(0, 0) = 1 となり、値は根に向かってさかのぼっていきます。
各ノードは1回ずつ訪問されるため、実行時間は O(n) です。呼び出しスタックには、現在の経路の各レベルにつき1つのフレームが保持されます。深さを h とすると O(h) で、ここでは最大14です。この上限があるため、この問題では再帰を安全に使えます。長い鎖のような形をしたポインタベースの木では、同じコードでも再帰制限に達します。Pythonではその制限は1000フレームです。
アルゴリズム
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回入り、1回出るため、時間計算量は O(n) です。キューに保持するのは一度に1つの階層分なので、最も幅の広い階層の幅を w とすると、空間計算量は 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明示的なスタックを使用した深さ優先探索
考え方
再帰呼び出しを一度も行わずに、再帰と同じように経路をたどれます。自分でスタックを用意し、各ノードを深さと一緒に保存します。ほかに深さを記憶しておく方法がないためです。まず、根を深さ 1 とする組 (0, 1) から始めます。
組を取り出し、その深さをこれまでの最大値と比べ、実際に存在する各子ノードを depth + 1 とともにプッシュします。木のすべてのノードは、そこに至る経路の長さを伴って一度だけプッシュされるため、取り出した深さの最大値が答えです。最初の例では、インデックス 9 の 6 は (9, 4) としてプッシュされ、それより深い組はありません。
時間計算量は O(n) です。スタックが保持するのは、現在の経路上にある処理待ちの兄弟ノードで、各レベルにつき最大でおよそ 1 つなので、空間計算量は O(h) です。再帰の場合と同じですが、呼び出しスタックがあふれる心配はありません。木が深くなる可能性があるときに使う方法で、ポインタベースの木にもそのまま適用できます。
アルゴリズム
(0, 1)をスタックにプッシュし、best = 0に設定します。- ペア
(i, depth)をポップし、bestをbestとdepthの大きい方に設定します。 - 子のインデックス
2*i+1と2*i+2が配列の範囲内にあり、-1でない場合は、それぞれを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
落とし穴と境界ケース
この問題での誤答の多くは、1つずれているか、空の位置をノードとして扱っていることが原因です。
- ノードではなく辺を数えている。ここでは1つのノードの深さは
1です。これに対して0を返したり、4ノードのパスに対して3を返したりすると、1つ足りません。 - 範囲チェックを省略している。配列の末尾近くにある葉の子インデックスは、配列が最後のノードの直後で終わっている場合、最後の要素を超えることがあります。
tree[child]を読み取る前にchild < nを確認してください。 - 配列の長さから深さを読み取っている。配列の末尾に余分な
-1の要素が含まれていることがあるため、その長さは実際のノードが存在する最も深いレベルより深いレベルに対応している場合があります。 -1を値として扱っている。これはノードがないことを示すため、スタックやキューに追加したり、数えたりしてはいけません。- 木が平衡であると仮定している。答えは最も長い枝に基づきます。たとえば、右側の位置がすべて空である14ノードの左側への連なりがある場合です。
- 幅優先探索版で、ループ内にキューのサイズを読み取っている。子を追加するとサイズが変わるため、処理のまとまりを始める前にサイズを保存してください。
- 配列のインデックスが1から始まるLuaとRで、オフセットを混同している。
2*i+1の計算ではノードのインデックスを0始まりのままにし、tree[i + 1]を読み取ってください。
よくある質問4
二分木の最大深さの時間計算量はどのくらいですか？
どの方法でも各ノードを1回ずつ訪問するため、時間計算量はO(n)です。深さ優先の方法では、探索中の経路のためにO(h)の追加領域を使用します。ここでhは深さです。幅優先の方法では、最も幅の広いレベルのためにO(w)を使用します。完全な木では、これはノード数の約半分になることがあります。
二分木の最大深さを求めるには、DFSとBFSのどちらを使うべきですか？
どちらも O(n) 時間で正しい答えを出します。深さ優先探索はコードが短く、深さに比例したメモリを使うため、幅が広く浅い木に適しています。幅優先探索はレベルを直接数え、最も幅の広いレベルに比例したメモリを使うため、深くて幅の狭い木に適しています。最小の深さを求める場合は、最初に見つけた葉で探索を終了できるため、幅優先探索が有利です。
再帰を使わずに二分木の最大深度を求めるにはどうすればよいですか？
ノードとその深さのペアを明示的なスタックに入れて使います。深さ1のルートから始め、ペアを取り出してその深さを記録し、各子ノードを深さに1を加えてスタックに入れます。取り出した深さの最大値が答えです。キューを使い、1レベルずつ処理してレベルごとに1を数える方法も使えます。
二分木の深さと高さの違いは何ですか？
ノードの深さはルートからそのノードまで下りるステップ数を数え、ノードの高さはそのノードから最も深い葉まで下りるステップ数を数えます。木の最大の深さとルートの高さは同じ数です。この問題ではノードを数えるため、ノードが1つだけの場合、その深さは1です。辺を数える本もあり、その場合は1少なくなります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def maxDepth(tree):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
期待値
4