Leetcode알고리즘 Binary Tree Inorder Traversal문제

오랜만에 알고리즘 포스팅을 해보려 합니다.

 

오늘은 Leetcode 94번 문제를 풀어볼 거예요.

제목은 Binary Tree Inorder Traversal이고 64.1%의 성공률을 가지고 중간 난이도입니다.

 

이진트리 중위 순회하는 문제입니다. 

 

문제를 풀기 전에 이진 트리 순회 개념부터 살펴봅시다.

트리 순회는 트리 구조에서 각각의 노드를 정확히 한 번만 체계적인 방법으로 방문하는 과정을 말합니다.

연결 리스트와 1차원 배열과 같은 선형 자료 구조에서는 한 가지의 논리적인 순회 방법이 존재하지만,

트리 구조의 순회에는 많은 방법이 존재합니다. 

 

전위 순회 (preorder)

1. 노드를 방문합니다.

2. 왼쪽 서브 트리를 전위 순회합니다.

3. 오른쪽 서브 트리를 전위 순회합니다.

전위 순회는 깊이 우선 순회라고도 합니다. 

preorder(node)
  print node.value
  if node.left ≠ null then preorder(node.left)
  if node.right ≠ null then preorder(node.right)

 

중위 순회 (inorder)

1. 왼쪽 서브 트리를 중위 순회합니다.

2. 노드를 방문합니다.

3, 오른쪽 서브 트리를 중위 순회합니다.

중위 순회는 대칭 순회라고도 합니다.

inorder(node)
  if node.left  ≠ null then inorder(node.left)
  print node.value
  if node.right ≠ null then inorder(node.right)

 

후위 순회(postorder)

1. 왼쪽 서브 트리를 후위 순회합니다.

2. 오른쪽 서브 트리를 후위 순회합니다.

3. 노드를 방문합니다.

postorder(node)
  if node.left  ≠ null then postorder(node.left)
  if node.right ≠ null then postorder(node.right)
  print node.value

(출처 위키백과)

 

다시 문제를 살펴봅시다.

Given the root of a binary tree, return the inorder traversal of its nodes' values.

이진트리의 루트 노드가 주어지고 중위 순회를 하여 노드의 값들을 리턴하면 됩니다. 

 

예를 들어 위와 같이 인풋이 들어오면 중위 순회를 하여 1 3 2를 출력해주면 됩니다. 

 

다시 중위 순회 알고리즘을 살펴보면 아래와 같습니다.

1. 왼쪽 서브 트리를 중위 순회합니다.

2. 노드를 방문합니다.

3, 오른쪽 서브 트리를 중위 순회합니다.

 

스위프트 코드로 구현하면 아래와 같습니다. 

class Solution {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var answer = [Int]()

        guard let rootNode = root else {
            return []
        }
        
        func traversal(node: TreeNode) {
            if node.left == nil, node.right == nil {
                answer.append(node.val)
                return
            }
            // 왼쪽 노드가 있는 경우 왼쪽 서브 트리 중위 순회를 합니다.
            if let leftNode = node.left {
                traversal(node: leftNode)
            }

            // 노드를 방문합니다.
            answer.append(node.val)

            // 오른쪽 노드가 있는 경우 오른쪽 서브 트리 중위 순회를 합니다.
            if let rightNode = node.right {
                traversal(node: rightNode)
            }
        }

        traversal(node: rootNode)
        return answer
    }
}

전위 순회, 중위 순회, 후위 순회 동일한 로직으로 가고 순서만 변경해주면 됩니다.

 

코드를 제출하면 런타임 소요 시간과 메모리 사용량이 나옵니다.

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