21. Maximum Depth of Binary Tree

読了目安 約1分

Tree / LC 104 (Easy) — 二分木の最大の深さ。木の再帰の型を覚える。

問題

LeetCode 104. Maximum Depth of Binary Tree（Easy / カテゴリ: Tree）

二分木は、各ノードが左右最大 2 つの子を持つ木構造です。 その根 root が与えられるので、最大の深さを返します。 最大の深さとは、根から最も遠い葉（子を 1 つも持たないノード）までの経路上のノード数です。 空の木の深さは 0 です。

考え方

Swift 実装のポイント

• TreeNode は参照型の class で定義します。子が無い場所は nil なので、引数の型は TreeNode? です。
• guard let root = root else { return 0 } で空の木を最初に処理します。
• 再帰は自分自身のメソッドを maxDepth(root.left) のように呼ぶだけです。

class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        return 1 + max(maxDepth(root.left), maxDepth(root.right))
    }
}