문제 소개
하나의 이진 트리가 주어졌다고 가정해 보겠습니다. 특정 노드를 지나는 모든 루트-리프(root-to-leaf) 경로의 노드 값 합이 limit보다 작다면, 그 노드를 불충분한 노드(insufficient node)라고 정의합니다. 이 문제의 목표는 모든 불충분한 노드를 한 번에 삭제한 뒤, 남은 이진 트리의 루트를 반환하는 것입니다.
예를 들어 아래와 같은 트리가 있고 limit이 1이라고 해보겠습니다.
이때 기대되는 출력 트리는 다음과 같습니다.
접근 방법
이 문제는 재귀적 DFS(깊이 우선 탐색)로 자연스럽게 해결할 수 있습니다. 핵심 아이디어는 자식 노드로 내려가면서 남은 limit에서 현재 노드의 값을 차감하고, 리프 노드에 도달했을 때 조건을 판단하는 것입니다. 구체적인 단계는 다음과 같습니다.
- solve(root, limit) 메서드를 정의합니다.
- 현재 노드가 리프 노드라면(왼쪽·오른쪽 자식이 모두 없다면), 노드 값이 limit보다 작을 경우 null을 반환하고, 그렇지 않으면 해당 노드를 그대로 반환합니다.
- 왼쪽 자식이 존재하면 root.left를 solve(root.left, limit - root.val)의 결과로 갱신합니다.
- 오른쪽 자식이 존재하면 root.right를 solve(root.right, limit - root.val)의 결과로 갱신합니다.
- 처리가 끝난 후 왼쪽 또는 오른쪽 자식 중 하나라도 살아남았다면 루트를 반환하고, 둘 다 null이 되었다면 null을 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
구현 예제
class Solution(object): def sufficientSubset(self, root, limit): """ :type root: TreeNode :type limit: int :rtype: TreeNode """ if not root.left and not root.right: return None if root.val < limit else root if root.left: root.left = self.sufficientSubset(root.left, limit - root.val) if root.right: root.right = self.sufficientSubset(root.right, limit - root.val) return root if root.left or root.right else None
복잡도 분석
이 풀이는 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 재귀 호출 스택의 깊이는 트리의 높이에 비례하므로, 공간 복잡도는 최악의 경우(편향된 트리) O(n), 균형 잡힌 트리라면 O(log n)입니다.
입력
[1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14] 1
출력
[1,2,3,4,null,null,7,8,9,null,14]