Maximum Depth of Binary Tree

アルゴリズム概要

    3          ← 深さ 1
   / \
  9  20        ← 深さ 2
    /  \
   15   7      ← 深さ 3 (葉)

  1            ← 深さ 1
   \
    2          ← 深さ 2 (葉)

ステップバイステップ解説

入力例1（root=[3,9,20,null,null,15,7]）を使って、BFS反復版の動きを追います。

Python 実装

2つの実装パターンを提供します。 業務開発版（BFS）は再帰深度制限を回避するため本番環境に適しており、 競技プログラミング版（再帰DFS）は最もシンプルでコードが短い実装です。

from __future__ import annotations
from typing import Optional
from collections import deque

# ════════════════════════════════════════════════
# 業務開発版：反復 BFS（CPython 再帰制限を回避）
# ════════════════════════════════════════════════
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # エッジケース：空の木（ノードが1つもない）→ 深さ 0
        # 後続の deque 処理に None を入れないための早期リターン
        if root is None:
            return 0

        # deque を使う理由：
        #   list.pop(0) は先頭削除が O(n) だが
        #   deque.popleft() は O(1) で済む
        queue: deque[TreeNode] = deque([root])
        depth: int = 0  # 処理したレベルの数 = 深さ

        while queue:
            # この時点の len(queue) = 今のレベルのノード数
            # ループ前に固定することで「次のレベルのノードが
            # append されても影響を受けない」ようにする
            level_size: int = len(queue)

            for _ in range(level_size):
                node: TreeNode = queue.popleft()  # O(1)

                # 左・右の子が存在すれば次のレベルとしてキューへ
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)

            # 今のレベルを全部処理し終えた = 1段降りた
            depth += 1

        return depth


# ════════════════════════════════════════════════
# 競技プログラミング版：再帰 DFS（最もシンプル）
# ════════════════════════════════════════════════
class Solution2:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # ベースケース：None = 存在しないノードの深さは 0
        # "is None" を使う理由：
        #   通常のノードオブジェクトはvalの値にかかわらずtruthyですが、
        #   ノードが存在しない(None)ことを真偽値ではなく明示的に判定するためです。
        if root is None:
            return 0

        # max() は C実装の組み込み関数なので if文より高速
        # 「左の深さ」と「右の深さ」の大きい方 + 現在ノード分(+1)
        return 1 + max(
            self.maxDepth(root.left),
            self.maxDepth(root.right),
        )

初期状態: queue=deque([Node(3)]), depth=0

【レベル1】level_size=1
  popleft() → Node(3)
    left=Node(9)   → append → queue=[Node(9)]
    right=Node(20) → append → queue=[Node(9),Node(20)]
  depth=1

【レベル2】level_size=2
  popleft() → Node(9)
    left=None, right=None → 追加なし
  popleft() → Node(20)
    left=Node(15) → append → queue=[Node(15)]
    right=Node(7) → append → queue=[Node(15),Node(7)]
  depth=2

【レベル3】level_size=2
  popleft() → Node(15) → 子なし
  popleft() → Node(7)  → 子なし
  depth=3

queue=deque([]) → 空 → ループ終了
return 3 ✅

処理フローチャート

計算量分析

📖 用語集

このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください。