22. Minimum Depth of Binary Tree

読了目安約1分

Tree / LC 111 (Easy) — 最小の深さ。子が片方だけのノードの罠に注意。

この章の目次

問題

LeetCode 111. Minimum Depth of Binary Tree（Easy / カテゴリ: Tree）

二分木の根 root が与えられるので、最小の深さを返します。最小の深さとは、根から最も近い葉までの経路上のノード数です。葉は子を 1 つも持たないノードなので、子が片方だけのノードは経路の終点になりません。空の木は 0 を返します。

考え方

ヒント 1

最大の深さの max を min に変えるだけでは壊れます。根の左だけが nil の木（例: [1, 2]）で何が起きるか考えてください。

ヒント 2

左が nil のとき、深さ 0 として min を取ると「葉が無い側」を選んでしまいます。子が片方だけのノードでは、子がある側の部分木だけで深さを決めます。両方の子があるときだけ min を取ります。

Swift 実装のポイント

root.left == nil と root.right == nil の場合分けを先に書くと、min の誤用を防げます。
片方が nil のとき 1 + minDepth(root.right) のように、ある側だけを再帰します。
幅優先探索（BFS）で最初に見つかる葉の深さを返す解もあります。どちらも O(N) です。

模範解答

Swift
class Solution {
    func minDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        if root.left == nil { return 1 + minDepth(root.right) }
        if root.right == nil { return 1 + minDepth(root.left) }
        return 1 + min(minDepth(root.left), minDepth(root.right))
    }
}

計算量: O(N)。全ノードを 1 回ずつ訪れる可能性があります。