Python으로 구현하는 이진 트리 전위 순회(Preorder Traversal)

이진 트리가 하나 주어져 있고, 우리는 이 트리의 전위 순회(preorder traversal) 결과를 반환해야 합니다. 전위 순회란 '루트 → 왼쪽 서브트리 → 오른쪽 서브트리' 순서로 노드를 방문하는 순회 방식입니다.

예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.

이 트리에 대한 전위 순회 결과는 다음과 같습니다.

[3, 9, 20, 15, 7]

해결 접근 방법

이 문제는 재귀 호출 대신 스택(stack)을 활용한 반복(iterative) 방식으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

• 결과를 저장할 빈 리스트 res와 노드를 임시 보관할 스택 st를 생성합니다.
• 현재 탐색 노드 node를 루트(root)로 초기화합니다.
• node 또는 st가 비어 있지 않은 동안 다음을 반복합니다.
  • node가 null이 아닌 동안: 노드의 값을 res에 추가하고, 노드를 st에 push한 뒤, node를 왼쪽 자식으로 이동합니다.
  • st의 마지막 요소를 꺼내(pop) temp에 저장합니다.
  • temp의 오른쪽 자식이 존재하면, node를 그 오른쪽 자식으로 설정합니다.
• 모든 순회가 끝나면 res를 반환합니다.

핵심 아이디어는 왼쪽 경로를 따라 내려가면서 값을 먼저 기록하고, 더 이상 왼쪽으로 갈 수 없으면 스택에서 이전 노드를 꺼내 오른쪽 서브트리로 이동하는 것입니다. 이렇게 하면 전위 순회 순서를 정확히 유지할 수 있습니다.

다음 구현 예제를 통해 더 잘 이해해 보겠습니다.

예제 코드

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):
            temp.left = TreeNode(data)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            temp.right = TreeNode(data)
            break
        else:
            que.append(temp.right)
def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree
class Solution(object):
    def preorderTraversal(self, root):
        res = []
        st = []
        node = root
        while node or st:
            while node:
                if node.data != None:
                    res.append(node.data)
                st.append(node)
                node = node.left
            temp = st[-1]
            st.pop()
            if temp.right:
                node = temp.right
        return res
ob1 = Solution()
head = make_tree([3,9,20,None,None,15,7])
print(ob1.preorderTraversal(head))

입력

[3,9,20,null,null,15,7]

출력

[3, 9, 20, 15, 7]