[DFS - 재귀, 후위 순회] LeetCode 104번 문제 학습

 

사용한 알고리즘

DFS를 사용하여 풀었음

 

• 왜 DFS냐?: 트리의 각 경로를 끝(리프 노드)까지 내려가서 깊이를 계산하고, 그 결과를 위로 올리면서 최대값을 찾으니까 깊이 우선 탐색 방식임
• 재귀: 각 노드에서 왼쪽과 오른쪽으로 재귀 호출을 해서 트리의 깊이를 탐색함

 

특히 후위 순회와 비슷한 형식으로 풀면 되는데, 왼쪽과 오른쪽 자식을 먼저 탐색한 뒤, 현재 노드에서 결과를 처리(최대값 선택)하는 방식이 후위 순회의 특징과 맞다고 생각함.

---

이 문제를 풀기 위해 필요한 알고리즘

재귀적 DFS (사용한 방식)

• 가장 직관적이고 간단하기 때문임
• 각 노드에서 왼쪽과 오른쪽 깊이를 재귀적으로 구하고, 최대값을 취하는 방식.
• 트리의 구조를 자연스럽게 활용 가능.

왜 DFS를 추천하나?

• 이 문제는 깊이를 구하는 게 목적이라, 끝까지 내려갔다가 올라오면서 최대값을 찾는 DFS가 코드도 간결하고 직관적이라 적합
• BFS는 레벨을 하나씩 확인하는 데 강점이 있지만, 이 문제에서는 굳이 레벨별로 나눌 필요가 없어서 DFS가 더 간단한 해결책임

BFS (너비 우선 탐색, Breadth-First Search)

• 큐를 사용해서 레벨 단위로 탐색하면서 깊이를 셀 수 있음
• 레벨이 곧 깊이가 되니까, 큐에 노드를 넣고 꺼내면서 레벨 수를 증가
• 시간 복잡도는 O(n), 공간 복잡도는 O(w) (w는 트리의 최대 너비).
• 구현이 조금 더 복잡하지만, 깊이를 레벨별로 확인할 때 유용.

 

package main

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

func checkTree(root *TreeNode, depth int) int {
	if root == nil {
		return depth - 1
	}
	left := checkTree(root.Left, depth + 1)
	right := checkTree(root.Right, depth + 1)
	if left > right {
		return left
	}
	return right
}

func maxDepth(root *TreeNode) int {
	return checkTree(root, 1)
}

func main() {
}​