LeetCode 104. Maximum Depth of Binary Tree
はじめに
LeetCode 「104. Maximum Depth of Binary Tree」の問題をGoで解きました。
問題
問題文
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
和訳
二分木のルートが与えられたとき、その最大深度を返す。
二分木の最大深度は、ルート・ノードから最も遠いリーフ・ノードまでの最長経路に沿ったノードの数である。
例
3
/ \
9 20
/ \
15 7
Input: root = [3,9,20,null,null,15,7]
Output: 3
Input: root = [1,null,2]
Output: 2
制約
- The number of nodes in the tree is in the range [0, 104].
- -100 <= Node.val <= 100
解答1：DFS（深さ優先探索、再帰）
二分木の最大深度を求める問題です。
まずDFSのアプローチで解きます。
左右の子の深さをそれぞれ求めて、大きい方＋１（現在のノード分） を返すという方針です。
左右の子の深さは再帰的に求めます。
ルートから最も深いリーフノードまでの経路は、左右どちらかのサブツリー内にあります。
そのため、それぞれのサブツリーの最大深度を再帰的に求め、その大きい方に現在のノード分（＋1）を加えることで全体の最大深度を求めることができます。
コード
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
leftDepth := maxDepth(root.Left)
rightDepth := maxDepth(root.Right)
return max(leftDepth, rightDepth) + 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
例１だと以下の図のような流れで呼び出されます。
maxDepth(3)
├── maxDepth(9)
│ ├── maxDepth(nil) → 0
│ └── maxDepth(nil) → 0
│ → max(0, 0) + 1 = 1
└── maxDepth(20)
├── maxDepth(15)
│ ├── maxDepth(nil) → 0
│ └── maxDepth(nil) → 0
│ → max(0, 0) + 1 = 1
└── maxDepth(7)
├── maxDepth(nil) → 0
└── maxDepth(nil) → 0
→ max(0, 0) + 1 = 1
→ max(1, 1) + 1 = 2
→ max(1, 2) + 1 = 3
計算量
- 時間的計算量：O(n)
- n はノード数（各ノードを1回ずつ訪れる）
- 空間的計算量：O(h)
- h は木の高さ（再帰呼び出しのスタックが木の高さ分使われる）
解答2：BFS（幅優先探索、Queue使用）
BFSでは Queue を使って木をレベル単位で探索します。
Queueに現在のレベルのノードを入れ、すべて処理したら1レベル進んだとみなして depth++ していきます。
Queue が空になったときの depth が最大深度になります。
BFSではレベルごとに進むため、「木の深さ」＝「何回レベルを進んだか」をカウントすれば最大深度を求められます。
コード
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root}
depth := 0
for len(queue) > 0 {
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
depth++
}
return depth
}
例１だと以下の図のような流れとなります。
[3] → depth = 1
↓
[9, 20] → depth = 2
↓
[15, 7] → depth = 3
↓
[] → 終了 → 答え = 3
計算量
- 時間的計算量：O(n)
- n はノード数（各ノードを1回ずつ訪れる）
- 空間的計算量：O(w)
- w は木の最大幅（Queue に最大で一度に保持するノード数）
参考
二分木の問題は、以下の記事でも紹介していますので、参考にしてください。
Discussion