Zenn
👌

104. Maximum Depth of Binary Tree

に公開
PHP
TypeScript
LeetCode
tech

2分木の根が与えられたとき、その最大深度を返します。

2分木の最大深度とは、根ノードから最も遠い葉ノードまでの最長パスに含まれるノードの数です。

例1:

入力: root = [3,9,20,null,null,15,7]
出力: 3

例2:

入力: root = [1,null,2]
出力: 2

こちらのコードは、PHPで書かれた2分木の最大深度を求めるためのクラスです。以下で詳しく解説します。

  • 2分木のノードを表すクラスです。
  • val：ノードの値
  • left：左の子ノード
  • right：右の子ノード
  • コンストラクタでノードを初期化します。
処理の流れ

  1. 基底条件：

    • 入力の根ノード ($root) が null の場合、深度は 0 です。

  2. 再帰処理：

    • 左部分木の深度を計算：$leftDepth = $this->maxDepth($root->left);
    • 右部分木の深度を計算：$rightDepth = $this->maxDepth($root->right);

  3. 最大深度を計算：

    • 左右の深度の大きい方を選び、+1 して返します。
    • +1 は現在のノード自身をカウントしています。

計算量

  • 時間計算量： O(N)
    • Nはノード数。すべてのノードを1回ずつ訪れるためです。
  • 空間計算量： O(H)
    • Hは木の高さ。再帰呼び出しの深さが木の高さに依存します。

実行例

入力：

    3
   / \
  9  20
    /  \
   15   7

$root = new TreeNode(3, 
    new TreeNode(9), 
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);

$solution = new Solution();
echo $solution->maxDepth($root); // 出力: 3

説明：

  • 根ノード 3 から最も深いパス（3 -> 20 -> 7 など）の長さは3です。
  • よって、出力は 3 になります。

Discussion