이진 트리의 루트 노드가 주어지고, 트리의 각 노드는 고유한 값을 가진다고 가정해 보겠습니다. 이때 to_delete 배열에 포함된 값을 가진 모든 노드를 삭제하면, 트리는 여러 개의 분리된 트리 집합, 즉 포리스트(forest)가 됩니다. 우리가 해야 할 일은 이 남은 포리스트를 구성하는 각 트리의 루트 노드들을 찾아내는 것입니다.
예를 들어 다음과 같은 이진 트리가 있다고 합시다.
만약 삭제할 값 배열 to_delete가 [3, 5]라면, 노드 3과 5가 제거된 후 결과는 다음과 같습니다.
해결 접근 방식
이 문제는 재귀적 순회(DFS)를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 결과를 저장할 배열 res를 정의합니다.
- solve() 메서드를 정의합니다. 이 메서드는 현재 노드(node), 삭제 대상 배열(to_delete), 그리고 해당 노드가 루트인지 여부를 나타내는 불리언 값(is_root)을 매개변수로 받으며, 다음과 같이 동작합니다.
- 노드가 null이면 null을 반환합니다.
- 현재 노드의 값이 to_delete 배열에 존재하는지 확인하여 flag를 설정합니다.
- flag가 false이고 is_root가 true라면, 현재 노드는 새로운 트리의 루트이므로 res에 추가합니다.
- 왼쪽 자식과 오른쪽 자식에 대해 solve()를 재귀 호출합니다. 이때 부모 노드가 삭제되는 경우(flag가 true) 자식들은 새로운 루트 후보가 되므로, flag 값을 is_root 인자로 전달합니다.
- 현재 노드가 삭제 대상이라면 None을 반환하고, 그렇지 않으면 노드 자신을 반환합니다.
- 메인 메서드에서 solve(root, to_delete, True) 형태로 호출하여 전체 순회를 시작합니다.
이제 실제 구현 예제를 통해 더 자세히 살펴보겠습니다.
예제 코드
class Solution(object): def delNodes(self, root, to_delete): """ :type root: TreeNode :type to_delete: List[int] :rtype: List[TreeNode] """ to_delete = set(to_delete) self.res = [] self.solve(root,to_delete,True) return self.res def solve(self,node,to_delete,is_root): if not node: return None flag = node.val in to_delete if not flag and is_root: self.res.append(node) node.left = self.solve(node.left,to_delete,flag) node.right = self.solve(node.right,to_delete,flag) return None if flag else node
위 코드에서 to_delete 리스트를 set으로 변환한 점에 주목하세요. 이렇게 하면 특정 값이 삭제 목록에 있는지 확인하는 연산의 시간 복잡도가 O(n)에서 O(1)로 개선되어 전체 알고리즘의 효율이 크게 향상됩니다.
입력
[1,2,3,4,5,6,7] [3,5]
출력
[[1,2,null,4],[6],[7]]
실행 결과를 보면, 값 3과 5를 가진 노드가 삭제된 후 세 개의 독립적인 트리 [1,2,null,4], [6], [7]의 루트들이 올바르게 반환된 것을 확인할 수 있습니다. 이 알고리즘의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(N)이며, 공간 복잡도 역시 재귀 호출 스택 깊이 기준으로 O(N)입니다.