문제 개요
이진 트리에 오류가 하나 있는 상황을 가정해 보겠습니다. 어떤 노드의 오른쪽 자식 포인터가 같은 레벨에 있는 다른 노드를 잘못 가리키고 있는 것입니다. 이 문제를 해결하려면 오류가 발생한 노드를 찾아낸 뒤, 그 노드가 잘못 가리키는 대상 노드를 제외한 나머지 자손 노드들과 함께 해당 노드를 삭제해야 합니다. 최종적으로 수정된 이진 트리의 루트 노드를 반환하면 됩니다.
예를 들어 입력이 다음과 같다고 해봅시다.
위 트리에서는 노드 4와 노드 6 사이에 잘못된 연결이 존재합니다. 즉, 노드 4의 오른쪽 자식 포인터가 같은 레벨의 노드 6을 가리키고 있습니다.
이 경우 출력, 즉 수정된 트리의 중위 순회(inorder) 결과는 다음과 같습니다.
2, 3, 5, 6, 7, 8,
노드 4는 노드 6을 잘못 가리키는 링크를 가지고 있으므로 트리에서 삭제됩니다.
해결 접근 방법
이 문제는 BFS(너비 우선 탐색)를 활용해 해결할 수 있습니다. 핵심 아이디어는 각 노드를 한 번씩만 방문해야 하는데, 큐에서 어떤 노드가 두 번째로 등장한다면 그것은 곧 잘못된 링크가 존재한다는 신호라는 점입니다. 구체적인 단계는 다음과 같습니다.
- q := 루트 노드를 담고 있는 새로운 데크(deque)를 생성합니다.
- p := 각 노드의 부모 정보를 저장할 새로운 딕셔너리(맵)를 생성합니다.
- visited := 방문 여부를 추적할 새로운 집합(set)을 생성합니다.
- q가 비어 있지 않은 동안 다음을 반복합니다.
- cur := q의 가장 앞쪽 요소를 꺼냅니다.
- 만약 cur가 visited에 이미 존재한다면(중복 방문 감지):
- grand_p, is_left := p[p[cur][0]] — cur의 부모를 조회하고, 그 부모의 부모(조부모) 정보와 부모가 왼쪽 자식인지 여부를 얻습니다.
- is_left가 참이면 조부모의 왼쪽 자식을 None으로 설정합니다.
- 그렇지 않으면 조부모의 오른쪽 자식을 None으로 설정합니다.
- 루트를 반환하고 종료합니다.
- visited에 cur를 추가합니다.
- cur의 왼쪽 자식이 존재하면:
- p[왼쪽 자식] := (cur, 1)로 기록합니다.
- q의 끝에 왼쪽 자식을 삽입합니다.
- cur의 오른쪽 자식이 존재하면:
- p[오른쪽 자식] := (cur, 0)으로 기록합니다.
- q의 끝에 오른쪽 자식을 삽입합니다.
- 모든 순회가 정상적으로 끝나면 루트를 반환합니다.
중복 방문이 감지되면, 해당 노드의 올바른 부모를 통해 조부모까지 거슬러 올라가 잘못된 링크를 가진 노드와 그 전체 서브트리를 연결 지점에서 제거하는 방식입니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
import collections
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def insert(temp, data):
que = []
que.append(temp)
while len(que):
temp = que[0]
que.pop(0)
if not temp.left:
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if not temp.right:
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def search_node(root, element):
if root == None:
return None
if root.data == element:
return root
res1 = search_node(root.left, element)
if res1:
return res1
res2 = search_node(root.right, element)
return res2
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.data, end=', ')
print_tree(root.right)
def solve(root):
q = collections.deque([root])
p, visited = dict(), set()
while q:
cur = q.popleft()
if cur in visited:
grand_p, is_left = p[p[cur][0]]
if is_left:
grand_p.left = None
else:
grand_p.right = None
return root
visited.add(cur)
if cur.left:
p[cur.left] = (cur, 1)
q.append(cur.left)
if cur.right:
p[cur.right] = (cur, 0)
q.append(cur.right)
return root
root = make_tree([5, 3, 7, 2, 4, 6, 8])
link_from = search_node(root, 4)
link_to = search_node(root, 6)
link_from.right = link_to
print_tree(solve(root))
입력
root = make_tree([5, 3, 7, 2, 4, 6, 8])
link_from = search_node(root, 4)
link_to = search_node(root, 6)
link_from.right = link_to
출력
2, 3, 5, 6, 7, 8,
동작 원리 정리
이 알고리즘은 시간 복잡도 O(n), 공간 복잡도 O(n)으로 트리의 모든 노드를 한 번씩 처리합니다. BFS 순회 중 동일한 노드가 두 번 큐에 들어오면, 부모 정보 딕셔너리 p를 이용해 해당 노드의 실제 부모와 조부모를 추적하고, 조부모의 자식 포인터를 None으로 설정하여 오류 노드와 그 서브트리 전체를 안전하게 제거합니다. 이렇게 하면 잘못 가리키던 대상 노드(예제에서는 노드 6)와 그 자손들은 그대로 유지되면서 트리가 정상적인 이진 트리 구조로 복원됩니다.