이진 트리가 하나 주어졌을 때, 두 번째로 깊은 리프 노드의 깊이를 구하는 프로그램을 작성해 보겠습니다. 가장 깊은 리프 노드가 여러 개 존재하는 경우에는, 그다음으로 높은 깊이에 있는 노드가 두 번째로 깊은 노드가 됩니다. 참고로 루트 노드의 깊이는 0입니다.
예를 들어 아래와 같은 트리가 입력으로 주어진다고 가정해 보겠습니다.
이 경우 출력값은 1이 됩니다. 두 번째로 깊은 노드가 3이고, 그 깊이가 1이기 때문입니다.
문제 해결 접근 방법
이 문제는 트리를 레벨 단위(레벨 순서 순회)로 탐색하면서 각 레벨에서 처음 만나는 리프 노드의 깊이를 추적하는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- 루트가 null이면 null을 반환합니다.
- 노드를 담을 새 리스트 nodes를 만들고 루트를 추가합니다.
- count := 0, prev := 0, now := 0으로 초기화합니다.
- nodes가 비어 있지 않은 동안 다음을 반복합니다.
- 새 리스트 new를 만들고 flag := True로 설정합니다.
- nodes의 각 노드에 대해 다음을 수행합니다.
- flag가 True이고 노드의 왼쪽·오른쪽 자식이 모두 null이라면(즉, 리프 노드라면) prev := now, now := count, flag := False로 갱신합니다.
- 왼쪽 자식이 존재하면 new의 끝에 추가합니다.
- 오른쪽 자식이 존재하면 new의 끝에 추가합니다.
- nodes := new로 교체하고 count를 1 증가시킵니다.
- 반복이 종료되면 prev를 반환합니다. 이 값이 곧 두 번째로 깊은 리프 노드의 깊이입니다.
여기서 now는 지금까지 발견한 가장 깊은 리프의 깊이를 저장하고, prev는 그 이전 값을 저장합니다. 따라서 반복이 끝난 시점의 prev가 두 번째로 깊은 리프 노드의 깊이가 됩니다.
예제 코드
아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
if root is None:
return None
nodes = []
nodes.append(root)
count = 0
prev = 0
now = 0
while nodes:
new = []
flag = True
for node in nodes:
if flag and (not node.left) and (not node.right):
prev = now
now = count
flag = False
if node.left:
new.append(node.left)
if node.right:
new.append(node.right)
nodes = new
count += 1
return prev
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))입력
root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(4) root.right.left = TreeNode(5) root.right.right = TreeNode(6) root.right.left.left = TreeNode(7) root.right.right.right = TreeNode(8)
출력
1
복잡도 분석
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 노드의 총개수입니다. 공간 복잡도는 각 레벨에 존재하는 최대 노드 수, 즉 트리의 최대 폭 w에 비례하여 O(w)이며, 한쪽으로 치우친 트리의 경우 O(n)까지 증가할 수 있습니다.