Balanced Binary Tree
配列 root には二分木が格納されています。ルートはインデックス 0 にあり、インデックス i の子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、末尾に余分な -1 が続く場合があります。
木が高さ平衡である場合、つまりすべてのノードで左部分木と右部分木の高さの差が最大でも 1 である場合は true を返し、それ以外の場合は false を返してください。部分木の高さは、最も長い下向きの経路にあるノードの数です。空の部分木の高さは 0 です。
関数
- rootinteger-array
- 二分木をレベル順に表し、空の位置には -1 を指定
- 戻り値boolean
- true：すべてのノードで、2つの部分木の高さの差が1以下の場合。そうでない場合はfalse。
制約
1 ≤ root.length ≤ 32767- 各
root[i]は-1または0 ≤ root[i] ≤ 105を満たす値です。 root[0]が-1になることはないので、木には少なくとも1つのノードがあります。- 配列の末尾には、最後のノードの後に余分な
-1の要素が含まれる場合があります。 - 空の位置の子も両方とも空で、深さは最大でも
14です。 - ノードの値はそれぞれ異なります。
例
- 入力
- root = [5, 2, 9, -1, -1, 7, 11]
- 出力
- true
- 説明
- ルートの左部分木は単一ノード
2で、高さは1です。右部分木の9、7、11の高さは2です。高さの差は1で、それ以外のすべてのノードは、左右の部分木の高さが等しくなっています。
- 入力
- root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
- 出力
- false
- 説明
- ルートの両側の高さはどちらも
3ですが、ノード3は条件を満たしません。左部分木1、0の高さは2で、右部分木は空です。
- 入力
- root = [4, 2, -1, 1]
- 出力
- false
- 説明
- ルートには左側に
2、1のチェーンがあり、高さは2で、右側には何もなく、高さは0です。差が2あるのは大きすぎます。
発展問題
明示的なスタックを使って、再帰なしでツリーを確認できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
木は根ではテストに合格しても、1つ下のレベルでは不合格になることがあります。そのノードで確認するには、どの2つの数値が必要ですか？
ノードの2つのサブツリーの高さが必要です。各ノードで高さを最初から計算すると、同じノードを何度もたどることになります。ノードを1回訪れるだけで、その高さと、その下のすべてが条件を満たしたかどうかの両方を親に伝えられるでしょうか？
部分木の高さを返す後行順関数を作成してください。部分木が平衡していない場合は、
-1を返します。ノードでは、子が-1を返した場合、または2つの高さの差が1を超える場合は-1を返し、それ以外の場合は1 + max(left, right)を返します。
解説
このルールはすべてのノードに適用されるため、根が偶数に見える木でも、2つ目の例が3で示すように、下の方で条件を満たさないことがあります。後行順の走査では、各部分木の高さを一度だけ計算し、条件を満たさない箇所が見つかるとすぐにその結果を上位に伝えるため、計算量はO(n)です。
各ノードの高さを再計算する
考え方
定義をコードに落とし込みます。height(i)は空の位置では0で、それ以外では高い方の子より1大きくなります。実際の各ノードで2つの子の高さを比較し、それらの差が1を超える最初のノードが見つかったら、答えはfalseです。
各チェックでは、そのノードの下にある部分木全体をたどるため、各ノードはその上にあるノードの数だけたどられます。つまり、O(n·h)です。レベル数が最大14の場合、16,383ノードの完全二分木でも、処理ステップ数は約2 × 10^5です。n個のノードが連なる場合、処理コストはO(n²)になります。
アルゴリズム
- 配列の末尾を超えるインデックスまたは
-1に対してはheight(i)を0と定義し、実際のノードに対しては1 + max(height(2*i+1), height(2*i+2))と定義します。 - 実際のノードを保持する各インデックス
iを調べます。 height(2*i+1)とheight(2*i+2)の差が1を超える場合は、falseを返します。- 失敗することなくループが終了した場合は、
trueを返します。
def isBalanced(root):
n = len(root)
def height(i):
# The number of nodes on the longest downward path from index i.
if i >= n or root[i] == -1:
return 0
return 1 + max(height(2 * i + 1), height(2 * i + 2))
# Check every real node, measuring both subtrees from scratch.
for i in range(n):
if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
return False
return True高さまたは失敗を報告する1回の後行順走査
考え方
ノードでのチェックには、2つの部分木の高さが必要です。また、それらはノード自身の高さを返すためにも必要です。そのため、1回の後行順走査で両方を取得します。各呼び出しは、両方の子ノードから戻った後に、その部分木の高さを返します。
下位で発生した失敗も上へ伝える必要があります。実際の高さが負になることはないため、-1をその印として使います。子ノードが-1を返した場合、または子ノードの高さの差が1を超える場合、呼び出しは-1を返します。2つ目の例では、3は高さ2と0を確認して-1を返し、ルートは右側を訪問せずにそれを伝えます。
各ノードに入るのは1回だけなので、時間計算量はO(n)で、スタック上の呼び出し数はO(h)です。
アルゴリズム
check(i)を記述します。末尾を超えるインデックスの場合、または-1の場合は、0を返します。left = check(2*i+1)を計算します。-1の場合は、-1を返します。right = check(2*i+2)を計算します。-1の場合、またはleftとrightの差が1を超える場合は、-1を返します。- それ以外の場合は、
1 + max(left, right)を返します。 check(0)が-1でないかどうかを返します。
def isBalanced(root):
n = len(root)
def check(i):
# The height of the subtree at index i, or -1 if it is not balanced.
if i >= n or root[i] == -1:
return 0
left = check(2 * i + 1)
if left == -1:
return -1
right = check(2 * i + 2)
if right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
return check(0) != -1
落とし穴と境界ケース
- ルートだけを確認する。2つ目の例では、ルートの左右両方の高さが
3ですが、ノード3の高さの差は2です。 - 最も浅い葉と最も深い葉を比較する。高さ
6の最小の平衡木では、葉の深さは4と6であり、その中のすべてのノードが条件を満たします。 - 再帰を戻る途中で失敗を見失う。子が
-1を返し、親が1 + max(-1, 2)を計算すると、失敗が再び高さに変わってしまいます。 - 配列の長さを高さとして使う。末尾の
-1の要素によって、配列が木の深さより長くなります。 - LuaとRでは、配列は1から始まります。ノードのインデックスは
2*i+1のために0始まりのままにし、root[i + 1]を読み取ります。
よくある質問3
平衡二分木の時間計算量は何ですか？
1回のポストオーダー走査では各ノードに1回ずつ入るため、木の高さがhの場合、時間計算量はO(n)、スタック領域はO(h)です。各ノードで高さを再計算するとO(n·h)のコストがかかり、一直線につながった木ではO(n²)になります。
二分木において、高さが平衡しているとはどういう意味ですか？
すべてのノードで、左部分木と右部分木の高さの差は最大でも 1 です。AVL木は挿入と削除のたびにこの性質を回復するため、高さは O(log n) に保たれます。
完全二分木は常にバランスが取れていますか？
はい。完全木では、最後のレベルを除くすべてのレベルが埋まっており、最後のレベルは左から埋まるため、どのノードでも2つの部分木の高さの差は最大で 1 です。逆は成り立ちません。平衡木でも、最後のレベルの左側に隙間がある場合があります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isBalanced(root):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
root = [5, 2, 9, -1, -1, 7, 11]
期待される出力
true