[Algorithm] LeetCode - 102. Binary Tree Level Order Traversal (BFS)

 

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).

 

번역)

이진 트리의 루트가 주어지면 노드 값의 레벨 순서 순회를 반환합니다. (즉, 왼쪽에서 오른쪽으로, 레벨별로).

 

 

Topic: Tree, Breadth First Search, Binary Tree

Level: Medium

Accepted 1,127,671 / Submissions 1,873,375

---

[제한사항]

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

---

[입출력]

예시 1

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

 

예시 2

Input: root = [1]
Output: [[1]]

 

예시 2

Input: root = []
Output: []

---

[문제풀이]

/**
 * 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) {
    // return if root is null
    if (root == null) return [];
    
    let answer = [];
    let queue = [];
    
    queue.push(root);
    while (queue.length > 0) {
        //  check queue length (left, right)
        let len = queue.length;
        let level = [];

        for (let i = 0; i < len; i++) {
            // take out first node from each child (zero ~ fourth node)
            let node = queue.shift();
            level.push(node.val);
            
            // push child to the queue
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        // push nth level nodes
        answer.push(level);
    }
    return answer;
};

 

Idea: 

1. BFS니 Queue를 적극 활용

2. queue에 담긴 node를 순차적으로 빼낸다. (왼쪽부터)

3. node value를 넣고 left, right child node를 push

---

 

[Performance]