102. Binary Tree Level Order Traversal
레벨 순서 순회(level-order)는 모든 노드를 낮은 레벨부터 차례대로 순회한다.
레벨 순서 순회는 너비 우선 순회(breadth-first traversal)라고도 한다.
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
level-order는 BFS 탐색과 마찬가지로 큐를 사용한다. root 레벨부터 자식인 왼쪽, 오른쪽 노드 순으로 탐색한다. 큐를 모두 탐색한 것은 곧 레벨에 더이상 탐색할 노드가 없다는 것이므로 result
에 group
을 담아준다.
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (root === null) return []
const result = []
const queue = [root]
while (queue.length > 0) {
const size = queue.length
const group = [];
for (let i = 0; i < size; i++) {
const curr = queue.shift();
group.push(curr.val)
if (curr.left) queue.push(curr.left)
if (curr.right) queue.push(curr.right)
}
result.push(group)
}
return result
};