트리 순회(Tree traversal) 두 가지 구현 방법(재귀, 반복문)

 

트리를 순회하는 방법은 preorder, inorder, postorder로 크게 3가지가 있다. 여기서 소개하려고 하는 내용은 이러한 순회를 "어떻게" 구현하는지에 관한 것이다. 가장 보편적인 것은 물론 재귀를 이용하는 것이나, 반복문을 통해서도 얼마든지 구현 가능하다.

참고로 트리노드의 정의는 아래와 같다고 하자.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

 

편의상 inorder를 구현하는 것으로 한다.

 

재귀(Recursive)를 통한 구현

---

class Solution:
    # Recursive
    def recurse(self, node, ans):
        if not node:
            return
        if node.left:
            self.recurse(node.left, ans)
        ans.append(node.val)
        if node.right:
            self.recurse(node.right, ans)
        
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        self.recurse(root, ans)
        return ans

 

반복문(Iterative)을 통한 구현

---

반복문을 통한 구현은 stack을 사용하면 된다. 아래와 같은 트리를 inorder로 탐색하려고 한다.

이 때, stack의 상태는 아래와 같다. stack에서 pop해줄 때마다 읽어들인다. ans에 표시한 리스트가 바로 pop해줄 때마다 읽어들이는 것을 나타낸 것이다.

class Solution:
    
    # Iterative
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = [root]
        visit = [root]
        if root:
            while stack:
                x = stack[-1]
                if x.left and x.left not in visit:
                    stack.append(x.left)
                if not x.left or x.left in visit:
                    ans.append(x.val)
                    visit.append(x)
                    stack.pop()
                    if x.right:
                        stack.append(x.right)
            return ans
                    
        else:
            return []

 

관련문제

leetcode.com/problems/binary-tree-inorder-traversal/