LeetCode - Binary Tree Level Order Traversal

 

 

 

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

​

class Solution {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        
        var resultList: [[Int]] = []
        
        
        //1
        guard let node = root else {
            return resultList
        }
        
        //2
        var levelList: [Int] = []
        
        resultList.append([node.val])
        
        //3
        var queue: [TreeNode?] = []
        
        if let left = node.left {
            queue.append(left)
        }
        
        if let right = node.right {
            queue.append(right)
        }
        
        while true {
            //4
            queue.forEach {
                if let node = $0 {
                    levelList.append(node.val)
                }
            }
            
            
            //5
            if levelList.isEmpty {
                break
            }
            resultList.append(levelList)
            levelList.removeAll()
            
            //6
            var count = queue.count
            while count > 0, let node = queue.removeFirst() {
                count -= 1
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
        }
        return resultList
    }
}

1. 전달된 노드가 nil 일때는 빈 2차원 배열을 반환한다.

2. 각 층의 노드 값들을 모으는 1차원 배열로 2차원 배열 전달용으로 사용한다.

3. 노드를 레벨별로 접근하기 위한 자료형 queue로 사용할 예정이며 따로 자료구조는 만들지 않음, 루트 노드의 자식 노드들을 먼저 queue에 enqueue 함

4. queue를 순회하면서 해당 층에 있는 요쇼들을 1차원 배열에 등록함

5. while loop 중단점, levelList가 비어있으면 위 작업이 발생하지 않은 것으로 루프 중단 그 외 경우 진행하며 2차원 배열에 1차원 배열 등록 후 1차원 배열은 초기화 시켜준다.

6. queue에 등록된 요소들을 dequeue 할 때 동일 레벨의 요소만 dequeue 하기 위한 요소

​

---

트리 형 자료구조를 레벨별로 순회하는 방법을 Tree 자료 구조 할때 공부를 했었는데 요구하는 리턴 형태가 레벨별로 배열을 나열해야 하기 곤란했다. 지금 보니까 되게 별거 없네

처음으로 연결 리스트, 트리형 자료구조 문제 자력으로 풀었다. 근데 뭔가 불필요하게 장황한거 같은데 leetcode 솔루션이 유료라 확인은 못했다.. 사야하나...