[리트코드 94, 144, 145] 이진 트리 순회(binary tree traversal)

3개의 문제지만 모두 이진 트리 순회에 대한 문제이다. 이전 포스트에서 설명했던 트리 자료구조의 중위 순회(inorder), 전위 순회(preorder), 후위 순회(postorder) 에 대한 개념만 알고 있으면 풀기 쉬운 간단한 문제이다.

 간단하게 다시 설명해보자면 중위 순회는 나 자신이 가운데 즉, left -> root -> right 순으로 노드를 출력한다. 전위 순회는 나 자신을 시작으로 즉, root -> left -> right 순으로 출력된다.(root 를 가장 처음으로 방문하게 된다.)
마지막으로 후위 순회는 전위 순회랑 반대로 root를 가장 마지막으로 방문하게 되며, left -> right -> root 순으로 출력한다.

 

Example

이진 트리인 root 가 주어졌을때, 순회 방식에 따라 출력값을 리턴하라.

root 값이 아래와 같이 주어졌고, 중위 순회(inorder) 로 풀이해보면 다음과 같다.

이진 트리 (중위 순회)

Input: root = [1,null,2,3]
Output: [1,3,2]

코드 샘플

# python

# 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
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        answer = []
        
        def traverse(root: Optional[TreeNode]) -> None:
            if root is None: 
                return
            
            # inorder = left -> self -> right
            traverse(root.left)
            answer.append(root.val)
            traverse(root.right) 
            
        traverse(root)
        return answer


class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        answer = []
        
        def traverse(root: Optional[TreeNode]) -> None:
            if root is None:
                return
            
            # preorder = self -> left -> right
            answer.append(root.val)
            traverse(root.left)
            traverse(root.right)
            
        traverse(root)
        return answer
        
        
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        answer = []
        
        def traverse(root: Optional[TreeNode]) -> None:
            if root is None:
                return 
            
            # postorder = left -> right -> root
            traverse(root.left)
            traverse(root.right)
            answer.append(root.val)
            
        traverse(root)
        return answer

 

코드에 대해 간략히 설명하자면, 위에서 부터 중위 순회, 전위 순회, 후위 순회를 풀이한 것으로 재귀문을 통해 순서대로 노드를 방문하며 answer 배열에 담아 리턴하는 코드이다. travese() 함수는 더이상 방문할 노드가 없는 경우(if root is None) 리턴하여 빠져나오도록 한다.