비어 있지 않은 하나의 이진 트리가 주어졌을 때, 최대 경로 합(Maximum Path Sum)을 구하는 문제를 살펴보겠습니다.
여기서 '경로(path)'란 부모-자식 연결이 존재하는 임의의 시작 노드에서 시작하여 다른 노드까지 이어지는 노드들의 시퀀스를 의미합니다. 경로에는 반드시 최소 한 개 이상의 노드가 포함되어야 하며, 루트 노드를 반드시 거칠 필요는 없습니다.
예를 들어 다음과 같은 입력 트리가 있다고 가정해 보겠습니다.
이 경우 출력 결과는 32가 됩니다.
문제 해결 접근 방법
이 문제는 재귀적 후위 순회(post-order traversal) 방식으로 해결할 수 있습니다. 핵심 아이디어는 각 노드를 '경로가 꺾이는 지점(peak)'으로 간주하고, 그 지점을 통과하는 최대 경로 합을 계산하는 것입니다. 단계별로 살펴보면 다음과 같습니다.
- solve()라는 메서드를 정의하고, 이 메서드에 노드를 전달합니다.
- 노드가 null이거나 노드의 값이 0이면 0을 반환합니다.
- left := max(0, solve(노드의 왼쪽 자식)) 로 계산합니다.
- right := max(0, solve(노드의 오른쪽 자식)) 로 계산합니다.
- ans := max(ans, left + right + 현재 노드의 값) 으로 갱신합니다.
- 현재 노드의 값 + max(left, right) 를 반환합니다. 즉, 부모로 확장 가능한 일직선 경로만 위로 넘겨줍니다.
- 메인 메서드에서는 ans := -무한대로 초기화한 뒤 solve(root)를 호출하고, 최종적으로 ans를 반환합니다.
구현 예제
아래 구현 코드를 통해 더 잘 이해해 보겠습니다.
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution(object):
def maxPathSum(self, root):
self.ans = -float('inf')
self.solve(root)
return self.ans
def solve(self,node):
if not node or node.data == 0:
return 0
left = max(0,self.solve(node.left))
right = max(0,self.solve(node.right))
self.ans = max(self.ans,left+right+node.data)
return node.data + max(left,right)
ob = Solution()
root = make_tree([-10,9,10,None,None,15,7])
print(ob.maxPathSum(root))입력
[-10,9,10,None,None,15,7]
출력
32
동작 원리 정리
이 알고리즘의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)입니다. 공간 복잡도는 재귀 호출 스택 깊이에 의해 결정되며, 최악의 경우(편향된 트리) O(n), 균형 잡힌 트리의 경우 O(log n)입니다.
핵심 포인트는 두 가지입니다. 첫째, 음수 값을 가진 하위 경로는 전체 합을 감소시키므로 max(0, ...) 처리를 통해 무시한다는 점입니다. 둘째, 부모 노드로 경로를 확장할 때는 왼쪽 또는 오른쪽 중 하나만 선택할 수 있기 때문에 반환값은 node.data + max(left, right)가 된다는 점입니다. 이렇게 하면 모든 노드를 꺾임점으로 하는 경로를 빠짐없이 검사하면서 최댓값을 찾을 수 있습니다.