문제 소개
이진 트리가 하나 주어졌을 때, 임의의 노드와 그 자손(descendant) 노드 사이의 최대 절대 차이를 구하는 것이 목표입니다.
예를 들어 아래와 같은 이진 트리가 입력으로 주어진다면,
출력은 7이 됩니다. 루트 노드 1과 자손 노드 8 사이의 절대 차이 |8 − 1| = 7이 트리 전체에서 가장 크기 때문입니다.
풀이 아이디어: 깊이 우선 탐색(DFS)
핵심 아이디어는 간단합니다. 각 노드를 기준으로 그 서브트리(subtree) 안에 있는 값들의 최솟값과 최댓값을 재귀적으로 수집하면, 현재 노드와 자손들 사이의 차이는 다음 두 값 중 더 큰 값이 됩니다.
- 현재 노드 값 − 서브트리의 최솟값
- 서브트리의 최댓값 − 현재 노드 값
이 과정을 모든 노드에 대해 반복하면서 전역 변수 ans를 갱신하면 최종 답을 얻을 수 있습니다.
알고리즘 단계
- 노드를 인자로 받는 dfs() 함수를 정의합니다.
- 노드가 null이면 [양의 무한대(+inf), 음의 무한대(−inf)]를 반환합니다. min/max 연산에 영향을 주지 않는 중립값 역할을 합니다.
- left := dfs(왼쪽 자식), right := dfs(오른쪽 자식)로 양쪽 서브트리의 결과를 구합니다.
- res := [min(left[0], right[0], 노드 값), max(left[1], right[1], 노드 값)] — 현재 서브트리 전체의 최솟값과 최댓값입니다.
- ans := max(ans, 노드 값 − res[0], res[1] − 노드 값)으로 정답을 갱신합니다.
- res를 반환합니다.
- 메인 함수에서는 ans를 0으로 초기화한 뒤 dfs(root)를 호출하고 ans를 반환합니다.
구현 예제
class TreeNode:
def __init__(self, data, left = None, right = None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
def dfs(node):
if not node:
return [float("inf"), float("-inf")]
left = dfs(node.left)
right = dfs(node.right)
res = [min(left[0], right[0], node.val), max(left[1], right[1], node.val)]
self.ans = max(self.ans, node.val - res[0], res[1] - node.val)
return res
self.ans = 0
dfs(root)
return self.ans
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(5)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(8)
root.right.left.left = TreeNode(7)
root.right.left.right = TreeNode(4)
print(ob.solve(root))
입력
root = TreeNode(1)
root.left = TreeNode(5)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(8)
root.right.left.left = TreeNode(7)
root.right.left.right = TreeNode(4)
출력
7
복잡도 분석
시간 복잡도: 모든 노드를 정확히 한 번씩만 방문하므로 O(n)입니다.
공간 복잡도: 재귀 호출 스택의 깊이에 비례하며, 편향된(skewed) 트리의 경우 최악 O(n), 균형 잡힌 트리의 경우 O(log n)입니다.