Level：Medium

Topic：Tree、Breadth-First Search、Binary Tree

---

Description

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

給定一個binary tree，回傳一個每個level從左到右的array

Solution

題目有給定一個TreeNode資料結構，val代表root、left代表左節點的tree、right代表右節點的tree。 我的解法是創建一個obj採用 { level: array } 的方法去儲存接著loop所有values後即可得到答案。

// 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) {
        return [];
    }
    const queue = []
    const obj = {}
    function recursive(tree, level = 0) {
        if (tree.val != null) {
            if (obj[level]) obj[level].push(tree.val)
            else obj[level] = [tree.val]
        }
        if (tree.left) recursive(tree.left, level + 1)
        if (tree.right) recursive(tree.right, level + 1)
    }
    
    recursive(root);
    
    const result = []
    Object.values(obj).forEach((value) => result.push(value))
    return result;
};

Best Solution(Gemini提供)

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) {
        return [];
    }

    const result = [];
    const queue = [root]; // 1. 初始化佇列，放入根節點

    while (queue.length > 0) {
        const levelSize = queue.length; // 2. 獲取當前層的節點數量
        const currentLevelNodes = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift(); // 3. 從佇列中取出節點
            currentLevelNodes.push(node.val);

            // 4. 將當前節點的左右子節點（如果存在）放入佇列中
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        result.push(currentLevelNodes); // 5. 將當前層的所有節點值加入結果
    }

    return result;
};