[재귀 + DFS] LeetCode 111번 문제 학습

문제를 푼 과정

• 처음에는 최대 깊이를 구하는 로직으로 작성해서 틀렸음.
• 최소 깊이를 구하려고 작은 값을 선택했지만, 루트에서 따로 계산해서 실패함.
• 재귀 하나로 통합해서 리프까지의 최소 경로를 찾도록 수정함.

문제에 대한 설명

• 이 문제는 이진 트리의 최소 깊이를 찾는 문제임.
• 루트에서 가장 가까운 리프 노드까지의 깊이를 계산해야 함.
• 한쪽 자식이 없으면 그쪽은 무시하고 반대쪽 깊이를 구해야 함.

이 문제를 풀려면 어떤 알고리즘을 써야 하는지

• 재귀를 사용해서 트리의 깊이를 탐색해야 함.
• 리프 노드에 도달했을 때 최소 깊이를 계산해야 함.
• DFS를 활용해 모든 경로 중 가장 짧은 길이를 찾으면 됨.

---

package main

import "fmt"

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	if root.Left == nil && root.Right == nil {
		return 1
	}

	if root.Left == nil {
		return minDepth(root.Right) + 1
	}

	if root.Right == nil {
		return minDepth(root.Left) + 1
	}

	left := minDepth(root.Left)
	right := minDepth(root.Right)

	if left > right {
		return right + 1
	}
	return left + 1
}

func main() {
	// root = [3,9,20,null,null,15,7] // 한 줄로 변수를 선언
	root := &TreeNode{3, &TreeNode{9, nil, nil}, &TreeNode{20, &TreeNode{15, nil, nil}, &TreeNode{7, nil, nil}}}

	a := minDepth(root)

	fmt.Println(a)
}