문제 개요
이진 트리(binary tree)가 하나 있다고 가정해 보겠습니다. 우리는 재귀(recursion)를 사용하지 않고 중위 순회(inorder traversal) 방식으로 이 트리를 순회해야 합니다.
예를 들어 트리가 다음과 같다면,
중위 순회 결과는 [2, 5, 7, 10, 15, 20]이 됩니다.
접근 방법: 스택을 활용한 반복적 순회
재귀 대신 스택(stack)을 활용하면 반복문만으로 중위 순회를 구현할 수 있습니다. 핵심 아이디어는 왼쪽 자식을 따라 내려가면서 지나온 노드들을 스택에 저장해 두었다가, 더 이상 왼쪽으로 갈 수 없을 때 스택에서 꺼내 처리하는 것입니다.
단계별로 살펴보겠습니다.
- 초기화: 결과를 담을 배열
res와 노드를 임시 저장할 배열stack을 생성하고,curr을 루트(root) 노드로 설정합니다. - 무한 루프를 실행합니다.
current가 null이 아닌 동안 다음을 반복합니다.curr을 스택에 push하고,curr을 왼쪽 자식 노드로 이동합니다.
- 스택의 길이가 0이 되면 모든 노드를 방문한 것이므로
res를 반환합니다. - 스택에서 요소를 pop하여
node에 할당합니다. node의 값을res에 삽입합니다.curr을 오른쪽 자식 노드로 이동합니다.
구현 예제
더 잘 이해하기 위해 다음 파이썬 구현 코드를 살펴보겠습니다.
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 inorderTraversal(self, root):
res, stack = [], []
current = root
while True:
while current:
stack.append(current)
current = current.left
if len(stack) == 0:
return res
node = stack[-1]
stack.pop(len(stack)-1)
if node.data != None:
res.append(node.data)
current = node.right
return res
ob1 = Solution()
root = make_tree([10,5,15,2,7,None,20])
print(ob1.inorderTraversal(root))
입력
[10,5,15,2,7,null,20]
출력
[2,5,7,10,15,20]
정리
이 알고리즘은 각 노드를 정확히 한 번씩 push하고 pop하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 최악의 경우(편향된 트리) 스택에 모든 노드가 저장될 수 있으므로 O(n)입니다. 재귀 호출로 인한 스택 오버플로우 위험을 피하고 싶거나, 호출 오버헤드를 줄이고 싶은 경우 이러한 반복적(iterative) 접근 방식이 유용하게 활용됩니다.