파이썬으로 이진 트리에서 가장 빈도가 높은 하위 트리 합계 찾기

이진 트리가 주어졌을 때, 가장 자주 나타나는 하위 트리 합계(most frequent subtree sum)를 찾아야 합니다. 여기서 노드의 하위 트리 합계란 해당 노드 자신을 포함하여 그 아래에 있는 모든 노드 값의 합을 의미합니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

이 경우 출력은 3이 됩니다. 3이라는 합계가 총 두 번 나타나기 때문인데, 한 번은 왼쪽 리프 노드의 값으로, 또 한 번은 3 - 6 + 6의 계산 결과로 등장합니다.

해결 접근 방법

이 문제는 후위 순회(post-order traversal) 방식의 재귀 함수를 사용하면 간단하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• 합계의 빈도를 저장할 빈 딕셔너리(맵) count를 초기화합니다.
• 노드를 인자로 받는 getSum() 함수를 정의합니다.
• 노드가 null이면 0을 반환합니다.
• mySum = 왼쪽 자식의 합 + 오른쪽 자식의 합 + 현재 노드의 값으로 계산합니다.
• count[mySum] 값을 1 증가시켜 해당 합계의 출현 횟수를 기록합니다.
• mySum을 상위 호출로 반환합니다.
• 메인 로직에서 루트 노드를 대상으로 getSum(root)을 호출합니다.

모든 하위 트리 합계가 기록되면, 빈도가 가장 높은 합계를 반환하면 됩니다.

구현 예제

from collections import defaultdict
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):
        count = defaultdict(int)
        def getSum(node):
            if not node:
                return 0
            mySum = getSum(node.left) + getSum(node.right) + node.val
            count[mySum] += 1
            return mySum
        getSum(root)
        return max(count, key=count.get)

ob = Solution()
root = TreeNode(-6)
root.left = TreeNode(3)
root.right = TreeNode(6)
print(ob.solve(root))

입력

root = TreeNode(-6)
root.left = TreeNode(3)
root.right = TreeNode(6)

출력

3

복잡도 분석

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 재귀 호출에 따른 스택 공간이 필요하므로 공간 복잡도 역시 최악의 경우 트리의 높이에 비례하는 O(n)입니다. defaultdict(int)를 사용하면 새로운 키에 대한 초기화 없이도 빈도 카운팅을 편리하게 처리할 수 있습니다.