Python으로 이진 트리에 연결 리스트가 존재하는지 확인하는 방법

루트 노드가 root인 이진 트리와 헤드 노드가 head인 연결 리스트가 주어졌을 때, 해당 연결 리스트가 이진 트리 안에 존재하는지 확인해야 합니다. 트리의 일련의 노드들이 연결 리스트처럼 순서대로 연결되어 있고, 그 순서가 주어진 연결 리스트와 동일하다면 True를 반환하고, 그렇지 않다면 False를 반환합니다.

문제 예시

예를 들어 다음과 같은 입력이 주어진다고 가정해 보겠습니다.

이진 트리

연결 리스트

위 트리에서 루트(6) → 왼쪽 자식(7) → 오른쪽 서브트리의 리프(10) 경로가 연결 리스트 [6, 7, 10]과 정확히 일치하므로, 출력 결과는 True가 됩니다.

해결 접근 방식

이 문제는 KMP 알고리즘의 실패 함수(접두사-접미사 배열) 개념을 활용하여 효율적으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• 연결 리스트의 값을 저장할 빈 리스트 arr를 생성합니다.
• size는 arr의 길이입니다.
• -1로 초기화된 크기 (size + 1)의 배열 temp_arr를 만듭니다. 이 배열은 KMP의 실패 함수 역할을 합니다.
• 재귀 함수 helper(root, val)를 정의합니다.
  • val이 size보다 크거나 같으면 연결 리스트 전체를 찾은 것이므로 True를 반환합니다.
  • root가 None이면 더 이상 탐색할 수 없으므로 False를 반환합니다.
  • val을 1 증가시킵니다.
  • val이 0보다 크고 현재 노드의 값이 arr[val - 1]과 일치하지 않는 동안, 실패 함수를 이용해 val을 되돌립니다(val = temp_arr[val - 1] + 1). 이 과정 덕분에 경로가 중간에 어긋나도 이미 일치한 접두사 부분부터 이어서 탐색할 수 있습니다.
  • 왼쪽 자식 또는 오른쪽 자식에 대해 재귀 호출한 결과 중 하나라도 True이면 True를 반환합니다.
  • 그 외의 경우 False를 반환합니다.
• start를 head로 설정하고, 연결 리스트를 끝까지 순회하며 각 노드의 값을 arr에 추가합니다.
• 인덱스 1부터 size까지 반복하면서 KMP 실패 함수 테이블을 구축합니다.
  • temp_arr[node] = temp_arr[node - 1] + 1로 초기 설정 후, 값이 일치하지 않으면 테이블 값을 갱신하며 되돌아갑니다.
• 마지막으로 helper(root, 0)의 결과를 반환합니다.

구현 예제

아래 구현을 통해 더 잘 이해할 수 있습니다.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

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):
    node = TreeNode(elements[0])
    for element in elements[1:]:
        insert(node, element)
    return node

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def solve(root, head):
    arr = []
    start = head
    while start:
        arr += (start.val,)
        start = start.next
    size = len(arr)
    temp_arr = [-1] * (size + 1)
    for node in range(1, size + 1):
        temp_arr[node] = temp_arr[node - 1] + 1
        while temp_arr[node] > 0 and arr[node - 1] != arr[temp_arr[node] - 1]:
            temp_arr[node] = temp_arr[temp_arr[node] - 1] + 1
    def helper(root, val):
        if val >= size:
            return True
        if not root:
            return False
        val += 1
        while val > 0 and root.val != arr[val - 1]:
            val = temp_arr[val - 1] + 1
        if helper(root.left, val) or helper(root.right, val):
            return True
        return False
    return helper(root, 0)

root = make_tree([6, 7, 8, 9, 10])
head = make_list([6, 7, 10])
print(solve(root, head))

입력

root = make_tree([6, 7, 8, 9, 10])
head = make_list([6, 7, 10])
print(solve(root, head))

출력

True

정리

이 알고리즘은 연결 리스트를 배열로 변환한 뒤 KMP 실패 함수를 미리 계산해 두기 때문에, 트리 탐색 중 불일치가 발생하더라도 처음부터 다시 비교하지 않고 최대한 일치한 지점에서 이어서 탐색할 수 있습니다. 시간 복잡도는 테이블 구축에 O(L)(L은 연결 리스트 길이), 트리 탐색에 O(N)(N은 트리 노드 수)이 소요되어 전체적으로 O(N + L)로 매우 효율적입니다.