이진 트리가 하나 주어졌다고 가정해 봅시다. 우리의 목표는 트리 안의 임의의 두 노드 사이에서 짝수 값으로만 구성된 가장 긴 경로를 찾는 것입니다.
예를 들어 입력이 다음과 같다면,
출력은 5가 됩니다. 이때 가장 긴 경로는 [10, 2, 4, 8, 6]입니다.
문제 해결 접근 방법
이 문제는 후위 순회(post-order traversal) 기반의 재귀 함수로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 노드를 기준으로 왼쪽과 오른쪽 서브트리에서 뻗어 나갈 수 있는 짝수 경로의 길이를 계산하고, 현재 노드의 값이 짝수인지 여부에 따라 전체 정답을 갱신하는 것입니다.
알고리즘 단계
정답을 저장할 변수
ans를 0으로 초기화합니다.노드를 인자로 받는
find()함수를 정의합니다.노드가 null이면 (-1, -1)을 반환합니다.
leftCnt:= find(노드의 왼쪽 자식) 반환값의 최댓값 + 1rightCnt:= find(노드의 오른쪽 자식) 반환값의 최댓값 + 1현재 노드의 값이 짝수라면:
ans:= max(ans, leftCnt + rightCnt + 1)(leftCnt, rightCnt)를 반환합니다.
그렇지 않다면(홀수라면):
ans:= max(ans, leftCnt, rightCnt)(-1, -1)을 반환하여 부모 쪽으로 경로가 이어지지 않도록 합니다.
메인 메서드에서
find(root)를 호출한 뒤ans를 반환합니다.
여기서 (-1, -1)을 반환하는 이유는, 홀수 노드를 만나면 그 지점에서 짝수 경로가 끊기기 때문입니다. 부모 입장에서는 해당 자식 쪽에서 유효한 경로를 얻지 못하므로 -1을 더해 0으로 처리됩니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
예제 코드
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def solve(self, root):
ans = 0
def find(node):
nonlocal ans
if not node:
return -1, -1
leftCnt = max(find(node.left)) + 1
rightCnt = max(find(node.right)) + 1
if node.val % 2 == 0:
ans = max(ans, leftCnt + rightCnt + 1)
return leftCnt, rightCnt
else:
ans = max(ans, max(leftCnt, rightCnt))
return -1, -1
find(root)
return ans
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))
입력
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
출력
5
복잡도 분석
이 알고리즘은 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)이며, 재귀 호출 스택 깊이에 비례하여 공간 복잡도는 최악의 경우 O(N), 균형 잡힌 트리의 경우 O(log N)입니다.