[LeetCode] 94번 - Binary Tree Inorder Traversal [Swift]

문제 링크

Binary Tree Inorder Traversal - LeetCode

문제

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

 

Example 1:

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

Output: [1,3,2]

 

Example 2:

Input: root = []

Output: []

 

Example 3:

Input: root = [1]

Output: [1]

 

Example 4:

Input: root = [1,2]

Output: [2,1]

 

Example 5:

Input: root = [1,null,2]

Output: [1,2]

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

문제 풀이

이 문제는 링크드 리스트로 주어지는 이진 트리를 inorder로 표현한 정수형 배열로 만드는 문제입니다.

inorder, 즉 중위순회로 만들라는 문제인데요, 중위순회의 경우에는 루트 노드가 중앙에 위치하게 되는 특징을 가집니다.

중위순회로 나타내게 되면 위와 같은 특징이 나타나는데요, 항상 루트 노드가 중앙에 오게 되며 루트 노트의 좌우에 존재하는 값들은 모두 실제 트리에서도 루트노드기준으로 좌,우에 위치하는 것을 볼 수 있습니다.

 

이러한 특징을 활용하여 주어진 링크드 리스트를 중위순회로 나타낼 수 있습니다.

위의 예를 가지고 다시 살펴보겠습니다.

일단 주어진 링크드 리스트에서 루트 값을 위의 그림과 같이 중앙에 둡니다. 그리고 왼쪽 노드, 오른쪽 노드의 값을 각각 좌, 우에 둡니다.

그럼 또 이번에는 자식노드들을 가지고 중위순회를 만듭니다.

위와 같이 자식노드를 기준으로도 루트, 왼쪽, 오른쪽을 나누고 중위순회를 계속 만들어내면됩니다.

지금 예는 레벨이 3인 트리라 여기서 끝나지만 레벨이 더 있다면 계속 동일한 방법으로 중위순회를 만들어내면 됩니다.

소스 코드

class Solution {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        }
        
        let leftTree = inorderTraversal(root?.left)
        let rootNode = [root!.val]
        let rightTree = inorderTraversal(root?.right)
        
        return leftTree + rootNode + rightTree
    }
}