Python으로 이진 트리에서 인접하지 않은 노드의 최대 합 구하기

문제 개요

이진 트리가 하나 주어졌다고 가정해 봅시다. 이때 부모와 자식 관계에 있는 두 노드는 동시에 선택할 수 없다는 조건 하에서, 선택한 노드 값들의 최대 합을 구하는 것이 목표입니다.

예를 들어 입력이 다음과 같다면,

출력은 17이 됩니다. 10, 4, 3은 서로 부모-자식 관계(인접)가 아니기 때문에 세 노드를 모두 함께 선택할 수 있기 때문입니다.

풀이 접근 방법

이 문제는 트리 위에서의 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 노드마다 두 가지 상태를 계산하는 것입니다.

• 현재 노드를 포함했을 때의 최대 합
• 현재 노드를 제외했을 때의 최대 합

구체적인 알고리즘 단계는 다음과 같습니다.

1. 함수 f()를 정의합니다. 이 함수는 노드를 매개변수로 받습니다.
2. 노드가 null이면 (0, 0)을 반환합니다.
3. (a, b) := f(노드의 왼쪽 자식)을 호출합니다. 여기서 a는 왼쪽 서브트리 전체의 최대 합, b는 왼쪽 자식을 제외한 상태의 최대 합입니다.
4. (c, d) := f(노드의 오른쪽 자식)을 호출합니다.
5. (max(노드의 값 + b + d, a + c), a + c) 쌍을 반환합니다. 즉, 현재 노드를 선택하면 자식 노드는 선택할 수 없으므로 b와 d를 사용하고, 현재 노드를 선택하지 않으면 자식의 최적해인 a와 c를 사용합니다. 두 경우 중 더 큰 값을 첫 번째 원소로 반환합니다.
6. 메인 메서드에서 f(root)를 호출하고, 반환된 쌍의 첫 번째 값을 결과로 돌려줍니다.

예제 코드

class TreeNode:
   def __init__(self, data, left=None, right=None):
      self.val = data
      self.left = left
      self.right = right

def f(node):
   if not node:
      return 0, 0
   a, b = f(node.left)
   c, d = f(node.right)
   return max(node.val + b + d, a + c), a + c

class Solution:
   def solve(self, root):
      return f(root)[0]

ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)
print(ob.solve(root))

입력

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)

출력

17

복잡도 분석

이 알고리즘은 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 재귀 호출 스택의 깊이는 트리의 높이에 비례하므로, 공간 복잡도는 O(h)(h는 트리의 높이)입니다. 균형 잡힌 이진 트리라면 O(log n), 편향된 트리라면 O(n)이 됩니다.