[LeetCode] 102번 - Binary Tree Order Traversal [Swift]

문제 링크

Binary Tree Level Order Traversal - LeetCode

문제

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

 

Example 1:

Input: root = [3,9,20, null, null,15,7]

Output: [[3],[9,20],[15,7]]

 

Example 2:

Input: root = [1]

Output: [[1]]

 

Example 3:

Input: root = []

Output: []

 

Constraints:

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

문제 풀이

이 문제는 주어진 이진트리를 레벨별로 나타내는 문제입니다.

주어진 예로 문제를 이해해보면 위와 같이 가장 깊은 레벨이 3인 이진트리의 각 레벨별 노드의 값을 배열로 나타내는 것인데요, 여기서 주의할 점은 왼쪽부터 차례대로 배열에 넣어야 한다는 점입니다.

 

일단 정답을 위한 2차원 정수 배열을 하나 만듭니다.

그리고 트리를 탐색하여 정답을 구하면 되는데, 이 문제에서 중요한 것은 레벨입니다.

따라서 탐색을 할 때 현재 보고 있는 노드의 레벨을 기억해주는 것이 중요합니다.

저는 이를 기억해주기 위해 재귀 함수를 사용했는데 매개변수로 다음 노드로 넘어갈 때마다 레벨을 1 증가시켜줬습니다.

또한 왼쪽부터 순서대로 넣어줘야 하기 때문에 왼쪽 노드부터 재귀를 수행해줬습니다.

 

정답 배열의 원소수가 만약 현재 보고 있는 레벨과 같다면 지금 보고 있는 노드가 해당 레벨의 가장 왼쪽 노드라는 뜻이기 때문에 해당 레벨의 배열을 새로 만들어서 정답 배열에 추가해주시면 됩니다.

 

즉 아래의 과정을 반복하면 됩니다.

1. 현재 레벨, 현재 노드를 가지고 재귀 함수를 시작합니다.
2. 정답 배열의 원소수가 현재 레벨과 같다면 해당 레벨의 가장 왼쪽 레벨이기 때문에 새로운 배열을 정답 배열에 추가해줍니다.
3. 정답 배열의 원소수가 현재 레벨과 같지 않다면 이미 해당 레벨의 배열이 있기 때문에 거기에 추가해줍니다.
4. 왼쪽부터 차례대로 넣어야 하기 때문에 현재 노드의 왼쪽 노드에 대하여 1번부터 다시 시작합니다.
5. 현재 노드의 오른쪽 노드에 대하여 1번부터 다시 시작합니다.

 

소스 코드

class Solution {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        var result: [[Int]] = []
        if root == nil {
            return []
        }
        func checkLevel(level: Int, node: TreeNode?) {
            if node == nil {
                return
            }
            guard let val = node?.val else { return }
            
            // 현재 레벨에 해당하는 배열이 아직 없다면 지금 노드가
            // 해당 레벨의 가장 왼쪽 노드이므로 새로운 배열 행성
            if level == result.count {
                result.append([val])
                // 현재 레벨에 해당하는 배열이 있다면 거기에 바로 추가
            } else {
                result[level].append(val)
            }
            // 왼쪽, 오른쪽을 나눠서 재귀함수 수행
            checkLevel(level: level + 1, node: node?.left)
            checkLevel(level: level + 1, node: node?.right)
        }
        checkLevel(level: 0, node: root)
        
        return result
    }
}