直径、高さ、平衡木
両方の値を返すヘルパーを使い、1回のDFSで木の直径と高さを計算し、その木が高さ平衡かどうかを判定します。
「直径、高さ、平衡木」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
二分木の高さ
二分木の高さ（または最大深さ）とは、根から任意の葉までの最長経路の長さです。これは再帰的に計算できます。任意のノードの高さは1 + max(height(left), height(right))であり、nullノードの基底ケースは0です。この後行順の計算は、直径、平衡性の確認、AVL木の回転の基礎となります。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root)) # 4直径：最長経路
二分木の直径とは、任意の2つのノード間にある最長経路の長さです（根を通る場合も通らない場合もあります）。経路の長さは辺の数で測ります。任意のノードを通る直径はheight(left) + height(right)です。木全体の直径は、すべてのノードについてこの値の最大値を取ったものです。
def diameter_of_binary_tree(root):
max_diameter = [0] # use list to allow closure mutation
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Diameter through this node
max_diameter[0] = max(max_diameter[0], left_h + right_h)
return 1 + max(left_h, right_h) # height for parent
dfs(root)
return max_diameter[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root)) # 3直径を求める1回のDFS走査
素朴な方法では各ノードでheight()を呼び出すため、平衡木でもO(n²)になります。最適な解法では、1回のDFS走査で高さを計算しながら直径を更新します。重要なポイントは、再帰関数dfs()が同時に2つの役割を果たすことです。親に対して高さを返す一方で、副作用として全体の最大直径を更新します。この二重目的の後行順パターンは、多くの木の問題で登場します。
# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
if not root:
return 0
through_root = height(root.left) + height(root.right)
in_left = diameter_naive(root.left)
in_right = diameter_naive(root.right)
return max(through_root, in_left, in_right)
# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')平衡二分木の確認
二分木が高さ平衡であるとは、すべてのノードについて、左部分木と右部分木の高さの差が高々1であることです。力任せの方法では各ノードでheight()を呼び出すため、O(n²)になります。最適な方法では、同じ1回の走査のテクニックを使います。「平衡していない」ことを示す番兵値として-1を返して上方向へ伝播させ、どこかのノードで不平衡が見つかった時点で早期に打ち切ります。
def is_balanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1 # propagate early exit
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1 # unbalanced here
return 1 + max(left, right) # height if balanced
return check(root) != -1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5) # too deep on left
print(is_balanced(root)) # False番兵値を返すパターン
番兵値（不平衡なら-1、または特別なタプル）を返すのは、DFSのヘルパーが2種類の情報、つまり計算結果と制約違反の有無を伝える必要がある場合によく使われるパターンです。例外を発生させたりグローバルフラグを使ったりする代わりに、戻り値の型にエラーを埋め込みます。この方法はすっきりしていて、グローバル状態を避けられ、他の再帰ヘルパーとも自然に組み合わせられます。
# General pattern: return (is_valid, computed_value)
def balanced_height(node):
if not node:
return True, 0
left_ok, left_h = balanced_height(node.left)
if not left_ok:
return False, 0 # short-circuit
right_ok, right_h = balanced_height(node.right)
if not right_ok:
return False, 0
balanced = abs(left_h - right_h) <= 1
return balanced, 1 + max(left_h, right_h)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h) # True 2ノード数と辺数で表す直径
問題文の定義には注意してください。LeetCode #543では直径を辺の数で測定しますが、ノードの数で測定する問題もあります。ノード数が必要な場合、あるノードを通る直径はheight(left) + height(right) + 1です（そのノード自体の分として1を加えます）。辺数が必要な場合は+1を省きます。コーディングを始める前に、面接官へこの点を必ず確認してください。
def diameter_in_nodes(root):
max_path = [0]
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Path through this node in NODE count
nodes_through = left_h + right_h + 1
max_path[0] = max(max_path[0], nodes_through)
return 1 + max(left_h, right_h)
dfs(root)
return max_path[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root)) # 4 nodes: 4-2-1-3 or 5-2-1-3パスの合計：任意の根から葉への経路
パスの合計問題では、根から葉への経路のいずれかについて、合計が目標値と等しくなるかを判定します。DFSを使い、下へ進むたびに目標値から現在のノードの値を引きます。葉に到達したら、残りの目標値がその葉の値と等しいかを確認します。これは残りの合計をパラメータとして渡す先行順DFSであり、トップダウン再帰の典型的な例です。
def has_path_sum(root, target):
if not root:
return False
# Leaf node: check if we've exactly hit the target
if not root.left and not root.right:
return root.val == target
remaining = target - root.val
return (has_path_sum(root.left, remaining) or
has_path_sum(root.right, remaining))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5+4+11+2=22最大パス合計（難しいバリエーション）
最大パス合計（LeetCode #124）は、さらに難しい問題です。経路は根から葉への経路に限られず、任意のノードで開始・終了でき、値が負になる場合もあります。各ノードでは、ノード単体、ノード + 左の分岐、ノード + 右の分岐、ノード + 両方の分岐という4つの選択肢を検討します。このうち親へ伸ばせるのは最初の3つだけで、4つ目は全体の最大値の候補として確定します。
def max_path_sum(root):
max_sum = [float('-inf')]
def gain(node):
if not node:
return 0
# Only take positive contributions
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
# Best path through this node (can't go both ways upward)
max_sum[0] = max(max_sum[0], node.val + left + right)
# Return the best single-branch gain for parent
return node.val + max(left, right)
gain(root)
return max_sum[0]
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root)) # 42: 15+20+7AVL木と自己平衡
AVL木は、挿入や削除の後に回転を行うことで高さ平衡の性質を維持するBSTです。各ノードは平衡係数（height(right) - height(left)）を保持し、その値は{-1, 0, 1}の範囲に収まる必要があります。違反が発生した場合は、単回転または二重回転によってO(1)時間で平衡を復元できます。これにより、全体の高さをO(log n)に保ち、すべての操作をO(log n)で保証できます。
# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node
# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root
# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')対称な木の確認
二分木が対称であるとは、自分自身の鏡像になっていることです。再帰的に確認するには、軸を挟んで対応するすべてのノードについて、値が等しく、部分木同士が鏡像になっていることを調べます。is_mirror(left, right)というヘルパーを定義し、両方がnullなら問題なし、一方だけがnullなら不一致、値が等しければ内側と外側の部分木が鏡像かどうかを確認します。
def is_symmetric(root):
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right)
sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym)) # True
nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym)) # False高さと直径の理解
ヘルパー関数が高さを返すと同時にグローバルな結果を更新する単一走査のポストオーダーパターンは、直径、最大パス合計、平衡性チェック、goodノードのカウントなど、多くの問題で再利用できます。常に「各子から親が必要とする情報は何か」と考えてください。それが返り値です。「このノードで局所的に行う計算は何か」と考えてください。それによってグローバルな答えを更新します。この分解が、難しい木の問題に取り組むための重要なスキルです。
# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
result = [float('-inf')] # or 0 depending on problem
def dfs(node):
if not node:
return 0 # base return (height, count, etc.)
left_val = dfs(node.left)
right_val = dfs(node.right)
# --- Update global result using both children ---
candidate = left_val + right_val # example: diameter
result[0] = max(result[0], candidate)
# --- Return info needed by PARENT ---
return 1 + max(left_val, right_val) # example: height
dfs(root)
return result[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root)) # diameter = 2確認テスト
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、再帰的なポストオーダーDFSによる高さの計算、二つの目的を持つDFSヘルパーを使ってO(n)の1回の走査で行う直径の計算、早期終了用のセンチネルを使った平衡性のチェックを学びました。次はパス合計の問題と最低共通祖先に取り組みます。
よくある質問
「直径、高さ、平衡木」レッスンは無料ですか？
はい。「直径、高さ、平衡木」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「直径、高さ、平衡木」で何を学びますか？
両方の値を返すヘルパーを使い、1回のDFSで木の直径と高さを計算し、その木が高さ平衡かどうかを判定します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「直径、高さ、平衡木」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。