파이썬으로 방향 이동 목록을 활용해 이진 트리 탐색하는 방법

문제 소개

이진 트리와 "R"(오른쪽), "L"(왼쪽), "U"(위)로 구성된 문자열 목록 moves가 주어졌다고 가정해 보겠습니다. 루트 노드에서 시작하여 moves의 각 이동 명령을 순서대로 수행하며 트리를 탐색해야 합니다. 각 명령의 의미는 다음과 같습니다.

• "R": 오른쪽 자식 노드로 이동
• "L": 왼쪽 자식 노드로 이동
• "U": 부모 노드로 이동

예를 들어, 아래와 같은 이진 트리가 있고 입력이 ["R", "R", "U", "L"]이라면 최종적으로 도착하는 노드의 값인 3이 출력됩니다.

해결 접근 방법

이 문제는 스택(Stack) 역할을 하는 리스트를 활용하면 간단하게 해결할 수 있습니다. 부모 노드로 돌아가야 할 때 스택에 저장해 둔 이전 노드를 꺼내면 되기 때문입니다. 단계별 과정은 다음과 같습니다.

1. 빈 리스트 past를 생성합니다.
2. moves의 각 이동 명령에 대해 다음을 수행합니다.
   • 현재 노드를 past의 끝에 추가합니다.
   • 명령이 "L"이면 현재 노드를 왼쪽 자식 노드로 변경합니다.
   • 명령이 "R"이면 현재 노드를 오른쪽 자식 노드로 변경합니다.
   • 그 외의 경우("U")에는 past의 마지막 요소를 제거한 뒤, 그 직전 요소를 꺼내 현재 노드로 설정합니다. 이는 부모 노드로 돌아가는 동작입니다.
3. 모든 이동이 끝난 후 현재 노드의 값을 반환합니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

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

class Solution:
    def solve(self, root, moves):
        past = []
        for move in moves:
            past.append(root)
            if move == "L":
                root = root.left
            elif move == "R":
                root = root.right
            else:
                past.pop()
                root = past.pop()
        return root.val

ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
traverse = ["R", "R", "U", "L"]
print(ob.solve(root, traverse))

입력

root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
["R", "R", "U", "L"]

출력

3

동작 원리 살펴보기

위 예제의 실행 과정을 단계별로 살펴보면 다음과 같습니다.

• "R": 루트(2)에서 오른쪽 자식(4)으로 이동
• "R": 노드 4에서 오른쪽 자식(5)으로 이동
• "U": 부모 노드(4)로 되돌아감
• "L": 노드 4에서 왼쪽 자식(3)으로 이동

최종적으로 노드 3에 도달하며, 결과값 3이 반환됩니다. 이처럼 스택을 활용하면 이동 경로를 효율적으로 추적하면서 부모 노드로의 복귀를 손쉽게 처리할 수 있습니다. 시간 복잡도는 이동 명령의 개수를 n이라 할 때 O(n)이며, 공간 복잡도 역시 O(n)입니다.