파이썬으로 이진 트리의 중위 순회가 회문인지 확인하는 프로그램

문제 개요

각 노드에 0부터 9 사이의 숫자가 저장된 이진 트리가 있다고 가정해 보겠습니다. 이때 이 트리의 중위 순회(inorder traversal) 결과가 회문(palindrome), 즉 앞뒤 어느 방향으로 읽어도 같은 수열인지 판별하는 프로그램을 작성해야 합니다.

예를 들어, 입력 트리가 다음과 같다면

중위 순회 결과가 [2, 6, 10, 6, 2]로 역순으로 읽어도 동일하므로 출력은 True가 됩니다.

알고리즘 접근 방법

스택을 활용한 반복적(iterative) 중위 순회로 트리를 탐색한 뒤, 그 결과가 회문인지 확인하는 방식으로 문제를 해결할 수 있습니다. 구체적인 절차는 다음과 같습니다.

• 루트가 None인 경우: 빈 트리는 항상 회문으로 간주되므로 True를 반환합니다.
• 새로운 스택(stack)을 생성하고, curr 변수에 루트 노드를 저장하며, inorder라는 새 리스트를 준비합니다.
• 스택이 비어 있지 않거나 curr가 None이 아닌 동안 다음 작업을 반복합니다:
  • curr가 None이 아닌 동안 curr를 스택에 push하고, curr를 왼쪽 자식 노드로 이동합니다.
  • 스택에서 요소를 pop하여 node에 저장합니다.
  • node의 값을 inorder 리스트의 끝에 추가합니다.
  • curr를 node의 오른쪽 자식 노드로 이동합니다.
• 순회가 완료되면 inorder와 이를 역순으로 뒤집은 결과를 비교하여 두 값이 같으면 True, 다르면 False를 반환합니다.

아래 예시 코드를 통해 더 자세히 살펴보겠습니다.

구현 예제 (Python)

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):
        if not root:
            return True
        stack = []
        curr = root
        inorder = []
        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            node = stack.pop()
            inorder.append(node.val)
            curr = node.right
        return inorder == inorder[::-1]

ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))

입력

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)

출력

True

복잡도 분석

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 또한 스택과 inorder 리스트가 노드 수에 비례하여 메모리를 사용하므로 공간 복잡도 역시 O(n)입니다. 여기서 n은 트리의 전체 노드 개수를 의미합니다.