문제 개요
이진 트리가 하나 주어졌다고 가정해 봅시다. 목표는 이 트리 안에서 값이 1씩 연속적으로 증가하거나 감소하는 가장 긴 경로의 길이를 찾는 것입니다.
예를 들어 입력이 아래와 같은 트리라면,
가장 긴 연속 수열이 [2, 3, 4, 5, 6]이므로 출력 결과는 5가 됩니다.
풀이 접근 방법
이 문제는 깊이 우선 탐색(DFS)과 재귀를 활용하여 해결할 수 있습니다. 핵심 아이디어는 각 노드마다 "증가 방향"과 "감소 방향"의 최장 경로 길이를 함께 추적하는 것입니다. 알고리즘은 다음과 같이 진행됩니다.
- 루트가 null이면 0을 반환합니다.
- maxPath := 0으로 초기화합니다.
- helper() 함수를 정의합니다. 이 함수는 노드를 인자로 받습니다.
- inc := 1, dec := 1로 초기화합니다. (각각 증가/감소 경로의 현재 길이)
- 노드의 왼쪽 자식이 null이 아니면 [left_inc, left_dec] := helper(왼쪽 자식)을 호출하고, 그렇지 않으면 [left_inc, left_dec] := [0, 0]으로 설정합니다.
- 오른쪽 자식에 대해서도 동일한 방식으로 처리합니다.
- 왼쪽 자식이 존재하고 (노드 값 − 왼쪽 자식 값) == 1이면 inc := max(inc, left_inc + 1)로 갱신합니다.
- 왼쪽 자식이 존재하고 (노드 값 − 왼쪽 자식 값) == -1이면 dec := max(dec, left_dec + 1)로 갱신합니다.
- 오른쪽 자식에 대해서도 같은 조건으로 inc와 dec를 갱신합니다.
- 양쪽 자식이 모두 존재하고 (왼쪽 자식 값 − 노드 값) == 1이며 (노드 값 − 오른쪽 자식 값) == 1이라면, 두 하위 경로를 하나로 이어붙일 수 있으므로 maxPath := max(maxPath, left_dec + right_inc + 1)로 갱신합니다.
- 반대로 (왼쪽 자식 값 − 노드 값) == -1이고 (노드 값 − 오른쪽 자식 값) == -1이라면 maxPath := max(maxPath, left_inc + right_dec + 1)로 갱신합니다.
- maxPath := max(maxPath, inc, dec)로 최종 갱신한 뒤 inc, dec를 반환합니다.
- 메인 메서드에서는 helper(root)를 호출한 후 maxPath를 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
구현 예제
class TreeNode:
def __init__(self, data, left = None, right = None):
self.val = data
self.left = left
self.right = right
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.val, end = ', ')
print_tree(root.right)
class Solution:
def solve(self, root):
if not root:
return 0
self.maxPath = 0
def helper(node):
inc, dec = 1, 1
if node.left:
left_inc, left_dec = helper(node.left)
else:
left_inc, left_dec = 0, 0
if node.right:
right_inc, right_dec = helper(node.right)
else:
right_inc, right_dec = 0, 0
if node.left and node.val - node.left.val == 1:
inc = max(inc, left_inc + 1)
elif node.left and node.val - node.left.val == -1:
dec = max(dec, left_dec + 1)
if node.right and node.val - node.right.val == 1:
inc = max(inc, right_inc + 1)
elif node.right and node.val - node.right.val == -1:
dec = max(dec, right_dec + 1)
if (node.left and node.right and node.left.val - node.val == 1 and node.val - node.right.val == 1):
self.maxPath = max(self.maxPath, left_dec + right_inc + 1)
elif (node.left and node.right and node.left.val - node.val == -1
and node.val - node.right.val == -1):
self.maxPath = max(self.maxPath, left_inc + right_dec + 1)
self.maxPath = max(self.maxPath, inc, dec)
return inc, dec
helper(root)
return self.maxPath
ob = Solution()
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(9)
root.right.left.left = TreeNode(6)
print(ob.solve(root))
입력
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(9)
root.right.left.left = TreeNode(6)
출력
5
복잡도 분석
시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이 h에 비례합니다. 균형 잡힌 트리라면 O(log n), 편향된 트리라면 O(n)이 됩니다.