Diameter of Binary Tree
二分木が配列 tree にレベル順で格納されています。ルートはインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、配列の末尾に余分な -1 の要素が含まれる場合があります。木の直径、つまり任意の 2 つのノード間の最長経路に含まれる辺の数を返してください。その経路はルートを通る場合も、1 つの部分木の中にとどまる場合もあります。
関数
- treeinteger-array
- 二分木をレベル順に並べ、空の位置には -1 を指定します
- 戻り値integer
- 2つのノード間の最長経路上の辺の数
制約
1 ≤ tree.length ≤ 32767- 各
tree[i]は-1または0 ≤ tree[i] ≤ 1000を満たす値です。 tree[0]は決して-1ではないため、木には少なくとも1つのノードがあります。- 配列の末尾には、最後のノードより後に余分な
-1の要素が含まれる場合があります。 - 空の位置の子は両方とも空であり、深さは最大でも
14です。
例
- 入力
- tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
- 出力
- 4
- 説明
- パス
7、4、3、8、6（インデックス9、4、1、0、2）には、4つの辺で結ばれた5つのノードがあります。ルートで方向を変えます。左側に3つの辺、右側に1つの辺を下ります。
- 入力
- tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
- 出力
- 4
- 説明
- 経路
3、1、5、9、4には4本の辺があり、インデックス1の5で曲がります。ルートには右の子がないため、ルートを通る経路は左側を下る3本の辺だけになります。
- 入力
- tree = [6, -1, -1]
- 出力
- 0
- 説明
- 単一のノードには辺がありません。最長のパスはノード単独で、長さは
0です。
提出時に隠しテスト+12件
発展問題
直径の一方の端からもう一方の端までの経路そのもの、つまりノードの値を返すにはどうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
木の中のすべての経路には、上向きから下向きに変わる最高位のノードが1つあります。そのノードが分かれば、そこを通る経路の長さはどれくらいになり得るでしょうか？
ノード
iで曲がる経路は、左部分木へ下り、右部分木へ下ります。最大の場合、左の子の高さに右の子の高さを加えたものになります。高さは最長の下向き経路上のノード数を数え、空の位置の高さは0です。高さは1回の後順走査で下から上へ計算します。ノードの高さは
1 + max(left, right)です。ノードでleftとrightを保持している間に、答えをleft + rightで更新します。
解説
最長経路は根を通るとは限らないため、根の左右の高さを測るだけでは不十分です。どの経路にも、上向きから下向きに切り替わる最も高いノードが1つあり、あるノードで折り返す最長経路の長さは、そのノードの左の高さと右の高さの合計です。後行順の走査を1回行うことで、下から上へ各高さを計算しながら、途中のすべての折り返し点を調べることができ、計算量は O(n) です。
すべてのノードのペアを測定する
正しいが、最大のテストでは終わらない
考え方
まず、配列内をどのように移動するかです。インデックス i のノードは、左の子を 2*i+1 に、右の子を 2*i+2 に持つため、親は (i-1)/2 を切り捨てた位置にあります。インデックスが配列内にあり、その位置の値が -1 でない場合に限り、その位置は実在します。[8, 3, 6, 1, 4, -1, -1, -1, -1, 7] では、インデックス 9 の 7 の親はインデックス 4 にあり、その 4 の親はインデックス 1 にあります。
直径は2つのノード間の最大距離なので、すべての組み合わせを測定できます。インデックス a と b の間の距離を求めるには、大きい方のインデックスから毎回1段ずつルートへ向かって登り、両者が合流するまで続けます。大きいインデックスがより高いレベルにあることはないため、この手順で合流点を通り過ぎることはありません。ステップ数が辺の数です。9 と 2 の場合、9 は 4、続いて 1 へ登り、2 は 0 へ登り、1 は 0 へ登ります。合計4ステップです。
これは正しい方法ですが、遅いです。最大のテストケースは16383ノードの完全な二分木で、約 1.3 × 10^8 組み合わせがあり、それぞれの組み合わせで最大26ステップかかります。1つの答えを求めるのに数十億ステップもかかるため、制限時間を大幅に超えてしまいます。
アルゴリズム
- すべての実ノードのインデックスを集めます。
- 各ペア
(a, b)について、edges = 0に設定し、a == bになるまで繰り返します。大きい方のインデックスをその親に置き換え、edgesに1を加えます。 - 確認した
edgesの最大値を保持し、それを返します。
def diameterOfBinaryTree(tree):
nodes = [i for i, value in enumerate(tree) if value != -1]
best = 0
for x in range(len(nodes)):
for y in range(x + 1, len(nodes)):
a, b = nodes[x], nodes[y]
edges = 0
while a != b:
# A larger index is never higher up, so climb from it.
if a > b:
a = (a - 1) // 2
else:
b = (b - 1) // 2
edges += 1
best = max(best, edges)
return best各ノードで両方の高さを測定する
考え方
最も高いノード、つまり上向きに進むのが止まり、下向きに進み始めるノードを通る最長経路を考えます。そこから左側を可能な限り下り、右側も可能な限り下ります。height(c) は c から下向きに進む最長経路上のノード数を数えるものとし、空の位置では 0 とします。すると、ノード i で折り返す最長経路の辺の数は height(2*i+1) + height(2*i+2) になります。それぞれのノードにつながる辺が1本ずつあるためです。
そこで、すべてのノードを折り返し地点として試し、最良のものを記録します。2つ目の例では、インデックス 1 の 5 は左側（1、3）の高さが 2、右側（9、4）の高さも 2 で、辺が4本の経路になります。ルートは左側の高さが 3、右側の高さが 0 なので、辺は3本だけです。
height を呼び出すたびに部分木全体をたどり、各ノードはその上にある祖先ノードごとに再びたどられるため、処理量は O(n·h) です。ここでは h ≤ 14 なので十分高速ですが、ポインター木が鎖状の場合、h は n に達することがあり、同じ考え方では O(n²) のコストがかかります。最後の方法で取り除くのは、この高さの繰り返し計算による無駄です。
アルゴリズム
height(i)を定義します。空の位置なら0、そうでなければ1 + max(height(2*i+1), height(2*i+2))です。- すべての実ノード
iについて、height(2*i+1) + height(2*i+2)を計算します。 - これらの合計のうち最大のものを返します。
def diameterOfBinaryTree(tree):
n = len(tree)
def height(i):
# Nodes on the longest downward path from i; an empty spot has 0.
if i >= n or tree[i] == -1:
return 0
return 1 + max(height(2 * i + 1), height(2 * i + 2))
best = 0
for i in range(n):
if tree[i] != -1:
# The longest path that turns at node i goes down both sides.
best = max(best, height(2 * i + 1) + height(2 * i + 2))
return best高さを対象にした1回の後行順走査
考え方
ノードの高さは2つの子の高さだけで決まり、それらは転換点の判定に必要な2つの数値と同じです。そこで、下から順に一度だけ計算します。後順走査では、親を処理する前に両方の子の処理が終わります。各ノードでは、left と right が得られるので、left + right で答えを更新し、1 + max(left, right) を親に返します。
最初の例では、葉の 7 は 1 を返し、その上の 4 は 2 を返します。また、3 は 3 を返します。もう一方の子 1 の高さが 1 だからです。6 は 1 を返します。根では left + right = 3 + 1 = 4 が答えです。他のノードで得られる最大値は 3 で、1 + 2 = 3 です。
各ノードは一度ずつ訪問されるため、時間計算量は O(n) です。再帰の深さは木の高さと同じ O(h) で、レベルごとにおよそ1つのフレームが使われます。呼び出しが返す値（高さ）は最後に必要な値（経路の長さ）とは異なるため、答えは再帰の外にある変数に保持します。
アルゴリズム
best = 0を設定し、height(i)を記述します。空の位置の場合は、0を返します。left = height(2*i+1)とright = height(2*i+2)を計算します。bestを、bestとleft + rightの大きい方に設定します。1 + max(left, right)を返します。height(0)を呼び出し、bestを返します。
def diameterOfBinaryTree(tree):
n = len(tree)
best = 0
def height(i):
# Returns the height of node i and updates best on the way back up.
nonlocal best
if i >= n or tree[i] == -1:
return 0
left = height(2 * i + 1)
right = height(2 * i + 2)
best = max(best, left + right) # the longest path that turns at node i
return 1 + max(left, right)
height(0)
return best
落とし穴と境界ケース
多くの誤答は、数える対象を間違えるか、測定するノードを間違えています。
- 辺ではなくノードを数える。
7、4、3、8、6の経路には5つのノードがあり、長さは4です。また、ノードが1つだけの場合、直径は0です。 - ルートを通る経路だけを測る。2つ目の例では、ルートを通る最長経路は辺が3本で、答えは4です。
1の位置で折り返します。 - 再帰呼び出しから直径を返す。親ノードは、より長い経路を作るために子ノードの高さを必要とします。直径は別の変数で管理します。
- 高さの定義を混在させる。ノード数を数える高さを使い、空の位置を
0とすると、left + rightですでに辺の数になります。辺の数を数える高さでは、空の位置に-1を使い、left + right + 2とします。一方の定義を半分ずつ混ぜると、答えが1つまたは2つずれます。 - 配列の末尾を越えて読み取る。配列の末尾近くにある葉ノードでは、子ノードのインデックスが最後の要素を越えることがあります。末尾を越えるインデックスは空の位置として扱います。
- 配列のインデックスが1から始まるLuaとRで、オフセットを間違える。
2*i+1の計算ではノードのインデックスを0始まりにし、tree[i + 1]を読み取ります。
よくある質問4
二分木の直径の時間計算量はどれくらいですか？
後順走査による解法では各ノードを1回ずつ訪問するため、実行時間はO(n)で、再帰にO(h)の追加領域を使用します。ここでhは高さです。各ノードで高さを個別に計算するとO(n·h)のコストがかかり、木が鎖状の場合はO(n²)になります。
二分木の直径は常にルートを通りますか？
いいえ。最長経路は、たとえばルートの片側に短い枝があり、もう片側に深く枝分かれした部分木がある場合のように、完全に一方の部分木の中に収まることがあります。そのため、ルートだけでなく、各ノードで left + right を確認します。
直径はノード数で数えますか、それともエッジ数で数えますか？
ここでは、経路上の連続するノード間のリンクである辺の数で数えます。そのため、ノードが1つだけの場合、直径は0で、接続されたノードが2つの場合、直径は1です。ノード数で数える本もあり、その場合は1多くなります。1を加えたり引いたりする前に、問題でどちらが求められているか確認しましょう。
再帰を使わずに二分木の直径を求めるにはどうすればよいですか？
すべての子が親より先に来る順序でノードを訪問します。方法の一つは、ルートをスタックにプッシュし、ノードをポップしてリストに追加しながらその子をプッシュし、その後リストを逆順にたどることです。各ノードの高さを配列に格納し、各ノードで2つの子の高さを読み取り、その合計で答えを更新します。計算時間は引き続き O(n) です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def diameterOfBinaryTree(tree):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
期待値
4