문제 개요
이진 트리(binary tree)가 하나 주어졌을 때, 트리의 모든 리프(잎) 노드가 동일한 레벨(깊이)에 위치하는지 확인하는 프로그램을 작성해야 합니다.
예를 들어 아래와 같은 이진 트리가 입력으로 주어진다면,
모든 리프 노드가 같은 깊이에 있으므로 출력 결과는 True가 됩니다.
해결 접근 방법
이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 리프 노드에 도달했을 때의 깊이를 기록하고, 기록된 깊이 값들이 모두 같은지 검사하는 것입니다.
알고리즘의 단계는 다음과 같습니다.
- dfs() 함수를 정의합니다. 이 함수는 루트 노드(root)와 현재 깊이(d)를 매개변수로 받습니다.
- 루트 노드가 null이 아니라면 다음을 수행합니다.
- 왼쪽 자식과 오른쪽 자식이 모두 null이라면(즉, 리프 노드라면): 현재 깊이 d를 depth 리스트의 끝에 추가합니다.
- 그렇지 않다면:
- 왼쪽 자식에 대해 dfs(left, d + 1)을 재귀 호출합니다.
- 오른쪽 자식에 대해 dfs(right, d + 1)을 재귀 호출합니다.
- 메인 메서드에서는 다음을 수행합니다.
- depth := 새로운 빈 리스트를 생성합니다.
- dfs(root, 0)을 호출하여 탐색을 시작합니다.
- depth 리스트에 담긴 값이 오직 하나뿐이라면 true를 반환합니다. 즉, 모든 리프 노드의 깊이가 동일하다는 의미입니다.
구현 예제
아래 구현 예제를 통해 더 잘 이해할 수 있습니다.
class TreeNode: def __init__(self, value): self.val = value self.left = None self.right = None class Solution: def solve(self, root): self.depth = [] self.dfs(root, 0) return len(set(self.depth)) == 1 def dfs(self, root, depth): if root: if not root.left and not root.right: self.depth.append(depth) else: self.dfs(root.left, depth + 1) self.dfs(root.right, depth + 1) ob = Solution() root = TreeNode(5) root.left = TreeNode(4) root.left.left = TreeNode(2) root.right = TreeNode(10) root.right.left = TreeNode(7) root.right.right = TreeNode(15) print(ob.solve(root))
입력
root = TreeNode(5) root.left = TreeNode(4) root.left.left = TreeNode(2) root.right = TreeNode(10) root.right.left = TreeNode(7) root.right.right = TreeNode(15)
출력
True
동작 원리 살펴보기
위 예제에서 리프 노드는 값이 2, 7, 15인 세 개의 노드입니다. DFS 탐색 과정에서 각 리프 노드에 도달할 때의 깊이가 depth 리스트에 순서대로 저장되며, 세 노드 모두 깊이 2에 위치하므로 set(self.depth)의 길이는 1이 되어 최종적으로 True가 반환됩니다.
만약 어떤 리프 노드라도 다른 깊이에 존재한다면 depth 리스트에는 두 가지 이상의 서로 다른 값이 저장되어 False가 반환됩니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n) — 트리의 모든 노드를 한 번씩 방문합니다.
- 공간 복잡도: O(n) — 재귀 호출 스택과 리프 노드 깊이를 저장하는 리스트가 트리 크기에 비례하여 공간을 사용합니다.