ボトムアップDFS（番兵値-1）による O(n) 実装
💡 この問題を一言で言うと：「木のすべてのノードで、左右の枝の深さの差が1以内かどうかを判定する問題」
高さ均衡二分木（height-balanced binary tree）とは、全ノードで左右の部分木の高さの差が最大1であるような二分木です。 空の木（root = null）も高さ均衡として扱います。
⚠️ なぜ単純な方法では解けないのか
3
/ \
9 20
/ \
15 7
全ノードで左右の高さの差 ≤ 1 → true
1
/ \
2 2
/ \
3 3
/ \
4 4
ルートの左右の高さ差 = 2 → false
（空の木） root = null
空の木は定義上 均衡 → true
🧠 解法のアイデア：1パスで高さ計算と均衡チェックを同時に行う
葉ノード（子のないノード）から根ノードに向かってさかのぼりながら（ボトムアップ）、高さを返しつつ同時に均衡チェックも行います。 不均衡が見つかったら -1（番兵値）を返し、上位ノードへ伝播させます。 これにより各ノードをちょうど1回だけ訪問する O(n) が実現できます。
各ステップをクリックするか ▶ Play で自動再生できます。
📋 このコードの構造（先に全体像を把握しよう）
from typing import Optional
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def check_height(node: Optional[TreeNode]) -> int:
# ベースケース：空のノードは高さ0
# `is None` はPEP 8推奨。None はシングルトンなので is が正確
if node is None:
return 0
# 左サブツリーの高さを再帰で取得
left_height = check_height(node.left)
# 左が -1（不均衡検知済み）なら即座に -1 を返す（早期リターン）
if left_height == -1:
return -1
# 右サブツリーの高さを再帰で取得
right_height = check_height(node.right)
# 右が -1 のときも同様に伝播
if right_height == -1:
return -1
# このノードでの均衡チェック
# abs() はC実装の組み込み関数で高速
if abs(left_height - right_height) > 1:
return -1 # 番兵値 -1 を返して不均衡を上位へ知らせる
# このノードの高さ = max(左, 右) + 自分の1
# max() もC実装の組み込み関数で高速
return max(left_height, right_height) + 1
# check_height が -1 でなければ均衡している
return check_height(root) != -1▶ 入力例 [3,9,20,null,null,15,7] での動作トレース
check_height(3) 開始 ├─ check_height(9) → left=0, right=0, diff=0 ≤ 1 → return 1 │ left_height=1 (≠-1、継続) ├─ check_height(20) 開始 │ ├─ check_height(15) → return 1 │ │ left_height=1 (≠-1、継続) │ ├─ check_height(7) → return 1 │ │ right_height=1 (≠-1、継続) │ └─ abs(1-1)=0 ≤ 1 → return max(1,1)+1 = 2 │ right_height=2 (≠-1、継続) └─ abs(1-2)=1 ≤ 1 → return max(1,2)+1 = 3 check_height(root) = 3 3 != -1 → isBalanced = True ✅
▶ 不均衡ケース [1,2,2,3,3,null,null,4,4] での動作トレース
check_height(4) → 1 (左の4) check_height(4) → 1 (右の4) check_height(3) [左] → abs(1-1)=0 → return 2 check_height(3) [右] → abs(0-0)=0 → return 1 check_height(2) [左] → abs(2-1)=1 ≤ 1 → return 3 check_height(2) [右] → return 1 check_height(1) [ルート] left_height=3, right_height=1 abs(3-1) = 2 > 1 → return -1 ← 不均衡！ check_height(root) = -1 -1 == -1 → isBalanced = False ✅
🗺️ フローチャートの読み方
🔎 入力例 [3,9,20,null,null,15,7] でのフロー追跡
📖 Big-O 記法の読み方（n = ノード数が大きくなるにつれて処理時間がどう増えるかの目安）
| アプローチ | 時間計算量 | 空間計算量 | 備考 |
|---|---|---|---|
| ✅ ボトムアップDFS（番兵値-1） | O(n) | O(h) | 各ノードを1回だけ訪問。h=木の高さ（均衡木ではO(log n)、最悪O(n)） |
| ❌ トップダウン再帰（素朴） | O(n²) | O(h) | 高さ計算と均衡チェックを分離するため同じノードを繰り返し訪問してしまう |
| BFS（幅優先探索） | O(n) | O(n) | dequeのメモリ確保コストがある。実装も複雑になりやすい |
🔍 なぜこの計算量になるのか
時間計算量 O(n)：check_height
はすべてのノードをちょうど1回だけ訪問します。不均衡が見つかった瞬間に -1
を返す早期リターンにより、無駄な再帰呼び出しを省けています。
空間計算量 O(h)：再帰呼び出しのコールスタックが木の高さ h
分だけ積み重なります。均衡木では h = O(log n)、最悪の一直線の木では h = O(n)
になります。
このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください。
node is None
がベースケースで、高さ0を返します。
return
して処理を終える手法です。不均衡が確定した時点で右サブツリーを調べる必要がなくなるため、無駄な計算を省けます。
None、True、False
がこれにあたります。is None
が
== None
より正確で速い理由は、Noneがシングルトンだからです。