[LeetCode] 94. Binary Tree Inorder Traversal

안녕하세요

 

오늘은 리트코드 94번 Binary Tree Inorder Traversal 문제를 풀어보겠습니다.

 

주어진 바이너리 트리의 배열을 Inorder 로 출력하는 문제 입니다. Inorder Traversal은 이진 트리를 탐색하는 방법 중 하나로,  왼쪽 자식 노드 > 루트 노드 > 오른쪽 자식 노드 순으로 탐색하는 방법 입니다. 이후에 이진 트리와 다른 탐색 방법에 대해서도 정리해보겠습니다.

 

 

해당 문제는 재귀를 사용하여 푸는 방법과 스택을 사용하여 푸는 방법이 있습니다. 먼저 스택을 사용하여 풀어보겠습니다.

 

풀이 1.

스택(stack)은 Last in First out (LIFO) 구조를 가지는 자료구조로, 마지막에 들어간 요소가 가장 먼저 나오는 방식입니다. 스택을 이용하면 재귀적으로 함수를 호출하는 대신, 직접 트리를 순회할 수 있습니다. 이는 재귀와 동일한 순회 순서를 유지하지만, 스택 자료구조를 사용하여 순회를 관리합니다.

# Definition for a binary tree node.

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

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = [] # inorder traversal의 결과를 저장할 리스트
        stack = [] # 노드를 임시로 저장할 스택
        current = root # 현재 방문 중인 노드를 추적할 변수


        while current is not None or stack: # 모든 노드를 순회할 때까지 반복
            while current is not None:
                stack.append(current) # 현재 노드를 스택에 저장
                current = current.left # 왼쪽 자식 노드로 이동

            current = stack.pop() # 스택에서 가장 최근 노드를 pop
            result.append(current.val) # 그 노드의 값을 결과 리스트에 추가
            current = current.right # 오른쪽 자식 노드로 이동
        return result

풀이 2. 

다음은 재귀를 사용하는 방식입니다. 재귀(Recursion)는 함수가 자기 자신을 반복적으로 호출하는 프로그램 기법입니다. 재귀를 사용한 Inorder Traversal은 왼쪽 자식 노드 > 루트 노드 > 오른쪽 자식 노드 순서로 호출 스택(call stack)을 이용해 자동으로 방문 순서를 처리할 수 있습니다.

 

# Definition for a binary tree node.

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

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = [] # 결과를 저장할 리스트

        def inorder(node):
            if node is None: # 노드가 없으면 함수 종료
                return
            inorder(node.left) # 1. 왼쪽 자식 노드 순회
            result.append(node.val) # 2. 현재 노드 값 저장
            inorder(node.right) # 3. 오른쪽 자식 노드 순회

        inorder(root) # 재귀함수 호출
        return result

 

 

---

 

스택을 사용했던 첫 번째 풀이 방식은 재귀 호출 없이 트리를 순회하기 때문에 스택 오버플로우 문제를 피할 수 있습니다. 하지만 코드가 재귀 방식에 비해 더 복잡해질 수 있고, 스택을 직접 관리해야하기 때문에 추가적인 메모리 공간이 필요합니다.

 

재귀를 사용했던 두 번째 풀이 방식은 호출될 때마다 트리의 왼쪽 끝까지 탐색했다가 재귀가 끝난 후 오른쪽 서브트리를 탐색하는 방식입니다. 코드가 간결하고 직관적인 구조이지만, 트리가 매우 깊거나 크다면, 스택 오버플로우 현상이 발생할 수 있습니다. 호출 스택의 크기는 제한적이기 때문에 너무 많은 재귀 호출이 쌓이면 오류가 발생할 수 있습니다. 

 

++ 개념정리

* 스택 오버플로우 (Stack Overflow)

프로그램에서 재귀 함수 호출이 너무 많이 중첩되거나 함수가 너무 깊이 호출되었을 때, 시스템이 할당한 스택 메모리 공간을 초과하여 발생하는 오류입니다.

 

이는 재귀 함수 호출을 멈추는 기저 조건을 조정하거나, 재귀의 깊이를 제한하는 방식으로 해소할 수 있습니다.