문제 소개
모든 노드가 두 개의 자식을 가지는 무한한 이진 트리가 있다고 가정해 보겠습니다. 각 노드에는 행(row) 순서대로 번호가 매겨지는데, 홀수 번째 행(1행, 3행, 5행, ...)은 왼쪽에서 오른쪽으로, 짝수 번째 행(2행, 4행, 6행, ...)은 오른쪽에서 왼쪽으로 레이블이 붙습니다. 즉, 레이블이 지그재그 형태로 배치되는 것이죠.
이때 트리의 구조는 다음과 같이 그려집니다.
이렇게 구성된 트리에서 특정 노드의 레이블이 주어졌을 때, 루트 노드부터 해당 레이블을 가진 노드까지의 경로에 있는 레이블들을 순서대로 구하는 것이 목표입니다.
예를 들어 입력이 label = 14라면, 루트에서 14까지의 경로는 1 → 3 → 4 → 14이므로 출력은 [1, 3, 4, 14]가 됩니다.
핵심 아이디어
이 문제의 핵심은 트리의 레이블을 레벨 순서대로 하나의 배열(tree)에 채워 넣는 것입니다. 배열에 순서대로 저장하면 일반적인 힙(heap) 구조처럼 인덱스 i에 있는 노드의 부모는 항상 인덱스 i // 2에 위치한다는 성질을 활용할 수 있습니다. 따라서 목표 레이블의 위치에서 부모 인덱스를 따라 루트까지 거슬러 올라가면 곧바로 경로를 얻을 수 있습니다.
풀이 단계
- 두 배열 tree와 res를 준비하고, tree에는 0(더미 값)과 1(루트)을 넣습니다. odd := 1, current := 1, two := 2로 초기화합니다.
- label이 1이라면 원소가 하나뿐인 리스트 [1]을 그대로 반환합니다.
- 무한 루프를 돌며 각 레벨의 레이블을 tree에 채워 넣습니다.
- odd가 참일 때: max_val := current + two를 계산한 뒤, temp := max_val부터 시작하여 temp > current인 동안 temp를 tree에 삽입하고 1씩 감소시킵니다(오른쪽에서 왼쪽 방향). temp가 label과 같아지거나 tree의 마지막 원소가 label이면 루프를 빠져나오고, current := max_val로 갱신합니다.
- odd가 거짓일 때: temp := two부터 시작하여 temp가 0이 될 때까지 temp를 1씩 감소시키고 current를 1씩 증가시키며 tree에 삽입합니다(왼쪽에서 오른쪽 방향). current 또는 tree의 마지막 원소가 label과 같아지면 루프를 종료합니다.
- 한 레벨을 채울 때마다 two를 2배로 늘리고, odd의 값을 반전시킵니다.
- 목표 레이블을 찾았다면 index := len(tree) - 1로 설정합니다.
- index가 0이 아닌 동안 res에 tree[index]를 추가하고, index를 2로 나누어 부모 노드로 이동합니다.
- res를 역순으로 뒤집은 뒤 반환합니다. 이것이 루트부터 목표 노드까지의 최종 경로입니다.
Python 예제 코드
다음 구현을 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def pathInZigZagTree(self, label):
tree = []
res = []
tree.append(0)
tree.append(1)
odd = 1
current = 1
two = 2
if label == 1:
return [1]
while True:
if odd:
max_val = current + two
temp = max_val
while temp>current:
tree.append(temp)
if temp == label:
break
temp-=1
if tree[-1]== label:
break
current = max_val
else:
temp = two
while temp:
temp-=1
current+=1
tree.append(current)
if current == label:
break
if tree[-1]== label:
break
two*=2
odd = not odd
index = len(tree)-1
while index:
res.append(tree[index])
index//=2
res=res[::-1]
return res
ob = Solution()
print(ob.pathInZigZagTree(14))
실행 결과
입력:
14
출력:
[1, 3, 4, 14]
label = 14는 4번째 행에 위치하며, 루트 1에서 출발해 오른쪽 자식 3, 그다음 왼쪽 자식 4를 거쳐 14에 도달하는 경로가 정확히 출력되는 것을 확인할 수 있습니다.