트리 문제를 처음 보면 꽤 막막합니다.
배열은 앞에서부터 보면 되고, 문자열도 왼쪽에서 오른쪽으로 읽으면 됩니다.
그런데 트리는 모양이 갈라져 있습니다.
5
/ \
3 8
/ \ \
1 4 9
이런 구조를 보면 처음에는 이런 생각이 들 수 있습니다.
"왼쪽으로 먼저 가야 하나?" "오른쪽은 언제 보지?" "재귀는 어디서 끝나야 하지?"
이번 글에서는 이진 트리 문제를 풀 때 사용할 수 있는 가장 기본적인 재귀 사고법을 정리해보겠습니다.
목표는 복잡한 트리 문제를 바로 푸는 것이 아닙니다.
먼저 아래 흐름을 이해하는 것이 목표입니다.
현재 노드에서 할 일을 정하고, 왼쪽과 오른쪽 결과를 합친다.
이진 트리란?
이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리입니다.
보통 두 자식을 이렇게 부릅니다.
- 왼쪽 자식
- 오른쪽 자식
Python으로 아주 단순하게 표현하면 이런 형태입니다.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
여기서 각 노드는 세 가지 정보를 가집니다.
| 속성 | 의미 |
|---|---|
value | 현재 노드의 값 |
left | 왼쪽 자식 노드 |
right | 오른쪽 자식 노드 |
즉, 트리 문제는 보통 현재 노드를 기준으로 왼쪽과 오른쪽을 나누어 생각합니다.
트리 문제의 기본 생각법
이진 트리 재귀 문제는 보통 아래 순서로 생각하면 됩니다.
1. 현재 노드가 비어 있는지 확인한다.
2. 왼쪽 서브트리 결과를 구한다.
3. 오른쪽 서브트리 결과를 구한다.
4. 현재 노드 값과 왼쪽/오른쪽 결과를 합친다.
여기서 서브트리는 현재 노드 아래에 달린 작은 트리입니다.
예를 들어 아래 트리에서 루트는 5입니다.
5
/ \
3 8
/ \ \
1 4 9
왼쪽 서브트리는 이 부분입니다.
3
/ \
1 4
오른쪽 서브트리는 이 부분입니다.
8
\
9
트리 문제는 큰 트리를 한 번에 해결하려고 하면 어렵습니다.
대신 이렇게 생각합니다.
왼쪽 트리의 답을 알고,
오른쪽 트리의 답을 안다면,
현재 노드에서 최종 답을 만들 수 있을까?
이 질문이 재귀 풀이의 핵심입니다.
예제 1. 트리 안의 모든 값 더하기
먼저 쉬운 문제부터 보겠습니다.
문제
이진 트리의 루트 노드가 주어졌을 때, 트리 안에 있는 모든 노드 값의 합을 구하세요.
예를 들어 아래 트리가 있다고 하겠습니다.
5
/ \
3 8
/ \ \
1 4 9
모든 값을 더하면 다음과 같습니다.
5 + 3 + 8 + 1 + 4 + 9 = 30
따라서 정답은 30입니다.
어떻게 생각해야 할까?
현재 노드를 기준으로 생각해보겠습니다.
현재 노드 값은 5입니다.
왼쪽 서브트리의 합은 3 + 1 + 4 = 8입니다.
오른쪽 서브트리의 합은 8 + 9 = 17입니다.
그러면 전체 합은 이렇게 구할 수 있습니다.
현재 노드 값 + 왼쪽 합 + 오른쪽 합
즉:
5 + 8 + 17 = 30
이제 이 생각을 코드로 옮기면 됩니다.
재귀 종료 조건
트리 재귀에서 가장 먼저 정해야 하는 것은 종료 조건입니다.
노드가 없으면 더할 값도 없습니다.
그래서 None이면 0을 반환합니다.
if node is None:
return 0
이 한 줄이 없으면 재귀가 계속 내려가다가 에러가 날 수 있습니다.
Python 풀이
def sum_tree(node):
if node is None:
return 0
left_sum = sum_tree(node.left)
right_sum = sum_tree(node.right)
return node.value + left_sum + right_sum
코드 설명
1. 노드가 없으면 0 반환
if node is None:
return 0
비어 있는 위치는 더할 값이 없으므로 0입니다.
2. 왼쪽 합 구하기
left_sum = sum_tree(node.left)
왼쪽 자식 아래에 있는 모든 값을 더합니다.
3. 오른쪽 합 구하기
right_sum = sum_tree(node.right)
오른쪽 자식 아래에 있는 모든 값을 더합니다.
4. 현재 노드 값까지 더하기
return node.value + left_sum + right_sum
현재 노드 값과 왼쪽 결과, 오른쪽 결과를 합쳐서 반환합니다.
이게 트리 재귀의 기본 구조입니다.
예제 2. 트리의 높이 구하기
이번에는 합계가 아니라 높이를 구해보겠습니다.
문제
이진 트리의 루트 노드가 주어졌을 때, 트리의 높이를 구하세요.
여기서는 노드 개수를 기준으로 높이를 세겠습니다.
예를 들어 아래 트리의 높이는 3입니다.
5 ← 1층
/ \
3 8 ← 2층
/ \ \
1 4 9 ← 3층
어떻게 생각해야 할까?
현재 노드에서 높이를 구하려면 왼쪽 높이와 오른쪽 높이 중 더 큰 값을 알아야 합니다.
왜냐하면 트리의 높이는 가장 깊은 쪽을 기준으로 정해지기 때문입니다.
현재 트리 높이 = max(왼쪽 높이, 오른쪽 높이) + 1
여기서 + 1은 현재 노드 자신을 의미합니다.
Python 풀이
def tree_height(node):
if node is None:
return 0
left_height = tree_height(node.left)
right_height = tree_height(node.right)
return max(left_height, right_height) + 1
코드 설명
1. 노드가 없으면 높이 0
if node is None:
return 0
비어 있는 곳은 높이가 없습니다.
그래서 0을 반환합니다.
2. 왼쪽과 오른쪽 높이를 각각 구하기
left_height = tree_height(node.left)
right_height = tree_height(node.right)
왼쪽 트리의 높이와 오른쪽 트리의 높이를 각각 구합니다.
3. 더 깊은 쪽을 선택하고 현재 노드를 더하기
return max(left_height, right_height) + 1
왼쪽과 오른쪽 중 더 큰 높이를 고르고, 현재 노드 한 층을 더합니다.
예제 3. 특정 값이 트리에 있는지 찾기
이번에는 값이 존재하는지 확인하는 문제를 보겠습니다.
문제
이진 트리의 루트 노드와 찾고 싶은 값 target이 주어졌을 때,
트리 안에 target 값이 있으면 True, 없으면 False를 반환하세요.
예를 들어 아래 트리에서 4를 찾으면 결과는 True입니다.
5
/ \
3 8
/ \ \
1 4 9
반대로 7을 찾으면 결과는 False입니다.
어떻게 생각해야 할까?
현재 노드에서 확인할 것은 세 가지입니다.
- 현재 노드가 비어 있는가?
- 현재 노드 값이 찾는 값인가?
- 왼쪽이나 오른쪽에 찾는 값이 있는가?
즉, 현재 노드가 답이 아니더라도 왼쪽 또는 오른쪽 어딘가에 값이 있으면 됩니다.
Python 풀이
def contains_value(node, target):
if node is None:
return False
if node.value == target:
return True
return contains_value(node.left, target) or contains_value(node.right, target)
코드 설명
1. 노드가 없으면 False
if node is None:
return False
비어 있는 곳에는 찾는 값이 있을 수 없습니다.
2. 현재 노드 값 확인
if node.value == target:
return True
현재 노드의 값이 찾는 값이면 바로 True를 반환합니다.
3. 왼쪽 또는 오른쪽에서 찾기
return contains_value(node.left, target) or contains_value(node.right, target)
왼쪽에 있거나 오른쪽에 있으면 True입니다.
둘 다 없으면 False입니다.
트리 재귀 문제의 공통 패턴
지금까지 세 문제를 봤습니다.
- 모든 값 더하기
- 트리 높이 구하기
- 특정 값 찾기
문제는 달라도 구조는 비슷합니다.
def solve(node):
if node is None:
return 기본값
left_result = solve(node.left)
right_result = solve(node.right)
return 현재 노드와 left_result, right_result를 합친 값
트리 문제를 만나면 무작정 코드를 쓰기보다 아래 질문을 먼저 해보는 것이 좋습니다.
트리 문제를 풀 때 던질 질문
1. 노드가 비어 있으면 무엇을 반환해야 할까?
합계를 구하는 문제라면 0이 자연스럽습니다.
높이를 구하는 문제도 비어 있으면 0입니다.
값이 있는지 찾는 문제라면 False입니다.
즉, 문제마다 기본값이 달라집니다.
2. 현재 노드에서 해야 할 일은 무엇일까?
현재 노드 값을 더해야 할 수도 있고, 현재 노드 값과 target을 비교해야 할 수도 있습니다.
문제마다 현재 노드에서 해야 할 일이 다릅니다.
3. 왼쪽 결과와 오른쪽 결과를 어떻게 합칠까?
트리 재귀에서 가장 중요한 질문입니다.
예를 들어:
| 문제 | 왼쪽/오른쪽 결과 합치는 방법 |
|---|---|
| 값의 합 | 현재 값 + 왼쪽 합 + 오른쪽 합 |
| 높이 | max(왼쪽 높이, 오른쪽 높이) + 1 |
| 값 찾기 | 왼쪽 결과 or 오른쪽 결과 |
이 표처럼 문제마다 합치는 방식이 달라집니다.
초보자가 자주 헷갈리는 부분
1. 재귀를 끝까지 손으로 따라가려는 경우
처음 공부할 때는 손으로 따라가는 연습도 필요합니다.
하지만 문제를 풀 때 모든 호출을 끝까지 따라가면 금방 지칩니다.
트리 재귀는 이렇게 생각하는 것이 더 좋습니다.
왼쪽 결과는 이미 구해졌다고 믿고,
오른쪽 결과도 이미 구해졌다고 믿고,
현재 노드에서 어떻게 합칠지만 생각한다.
처음에는 이상하게 느껴지지만, 이 감각이 중요합니다.
2. None 처리를 빼먹는 경우
트리의 끝에는 자식이 없는 위치가 있습니다.
이 위치는 코드에서는 보통 None입니다.
그래서 재귀 함수 첫 부분에서 None 처리를 해줘야 합니다.
if node is None:
return 기본값
이 부분을 빼먹으면 에러가 나거나 재귀가 제대로 끝나지 않을 수 있습니다.
3. 왼쪽만 보고 오른쪽을 놓치는 경우
트리는 양쪽으로 갈라집니다.
그래서 대부분의 이진 트리 문제에서는 왼쪽과 오른쪽을 모두 봐야 합니다.
left_result = solve(node.left)
right_result = solve(node.right)
이 두 줄이 기본 뼈대가 되는 경우가 많습니다.
정리
이진 트리 문제는 처음에는 복잡해 보입니다.
하지만 재귀로 풀 때는 아래 순서를 먼저 생각하면 됩니다.
1. 노드가 비어 있을 때의 값을 정한다.
2. 왼쪽 결과를 구한다.
3. 오른쪽 결과를 구한다.
4. 현재 노드에서 두 결과를 합친다.
문제마다 반환값은 달라집니다.
- 합계를 구하면 숫자
- 높이를 구하면 숫자
- 값 존재 여부를 구하면 True 또는 False
하지만 큰 흐름은 비슷합니다.
트리 문제를 볼 때 가장 중요한 질문은 이것입니다.
왼쪽 결과와 오른쪽 결과를 알 때,
현재 노드에서는 무엇을 반환해야 할까?
이 질문에 답할 수 있으면 많은 트리 재귀 문제를 훨씬 편하게 접근할 수 있습니다.