乐趣区

关于javascript:102二叉树的层序遍历-算法leetcode附思维导图-全部解法300题

jiezi

零 题目：算法（leetcode，附思维导图 + 全副解法）300 题之（102）二叉树的层序遍历

一 题目形容


二 解法总览（思维导图）

三 全副解法

1 计划 1

1)代码：

// 计划 1“本人。2 个队列法”。// 思路：// 1）边界：若 root 为假值，则 间接返回 []。// 2）状态初始化：let resList = [], curLevel = 0, queue_1 = [root], queue_2 = []。// 3）外围：跟 2 个队列（queue_1、queue_2）状况，对该二叉树进行遍历解决。// 4）返回后果 resList。var levelOrder = function(root) {// 1）边界：若 root 为假值，则 间接返回 []。if (!root) {return [];
    }

    // 2）状态初始化：let resList = [], curLevel = 0, queue_1 = [root], queue_2 = []。let resList = [],
        curLevel = 0,
        queue_1 = [root],
        queue_2 = [];
    
    // 3）外围：跟 2 个队列（queue_1、queue_2）状况，对该二叉树进行遍历解决。while (queue_1.length !== 0) {const {val, left, right} = queue_1.shift();
        // 边界
        if (resList[curLevel] === undefined) {resList[curLevel] = [];}
        resList[curLevel].push(val);
        
        if (left) {queue_2.push(left);
        }
        if (right) {queue_2.push(right);
        }

        if (queue_1.length === 0) {
            curLevel++;
            // 注：以下 2 行 可简写成 [queue_1, queue_2] = [queue_2, []]。queue_1 = queue_2;
            queue_2 = [];}
    }

    // 4）返回后果 resList。return resList;
}

2 计划 2

1)代码：

// 解法 2“本人。1 个队列法（实质：计划 1 的优化版）”。// 思路：// 1）边界：若 root === null，则 间接返回 []。// 2）状态初始化：queue = [root], curLevel = 0, resList = []。// 3）外围：若 queue.length !== 0，则 循环解决。// 3.1）外围：解决本次 队列 queue 里的所有节点
// 并将各节点值放入以后档次的列表中。// 3.1.1）初始化本层列表。// 3.1.2）别离依据 左、右子树 状况，更新 queue 值。// 3.2）更新档次的值 curLevel++。// 4）返回后果 resList。var levelOrder = function(root) {// 1）边界：若 root === null，则 间接返回 []。if (root === null) {return [];
    }

    // 2）状态初始化：queue = [root], curLevel = 0, resList = []。let queue = [root],
        curLevel = 0,
        resList = [];
    
    // 3）外围：若 queue.length !== 0，则 循环解决。while (queue.length !== 0) {
        // 3.1）外围：解决本次 队列 queue 里的所有节点
        // 并将各节点值放入以后档次的列表中。const l = queue.length;
        for (let i = 0; i < l; i++) {const {val, left, right} = queue.shift();
            // 3.1.1）初始化本层列表。if (!resList[curLevel]) {resList[curLevel] = [];}
            resList[curLevel].push(val);
            // 3.1.2）别离依据 左、右子树 状况，更新 queue 值。if (left !== null) {queue.push(left);
            }
            if (right !== null) {queue.push(right);
            }
        }

        // 3.2）更新档次的值 curLevel++。curLevel++;
    }

    // 4）返回后果 resList。return resList;
}

3 计划 3

1)代码：

// 解法 3“递归”。// 参考：// 1）https://leetcode.cn/problems/binary-tree-level-order-traversal/solution/dai-ma-jian-ji-yi-chong-huan-bu-cuo-de-j-139f/

// 思路：// 1）状态初始化：curLevel = 0, curRoot = root, resList = []。// 2）外围：调用递归函数。// 3）返回后果 resList。var levelOrder = function(root) {
    // 递归函数
    const dfs = (curLevel = 0, curRoot = null) => {
        // 1）递归进口
        if (curRoot === null) {return;}

        // 2）递归主体
        const {val, left, right} = curRoot;

        // 2.1）初始化 本层的列表。if (!resList[curLevel]) {resList[curLevel] = [];}
        // 2.2）本层的列表塞入 以后的节点值。resList[curLevel].push(val);
        // 2.3）别离递归解决 左、右子树。dfs(curLevel + 1, left);
        dfs(curLevel + 1, right);
    };

    // 1）状态初始化：curLevel = 0, curRoot = root, resList = []。let curLevel = 0,
        curRoot = root,
        resList = [];

    // 2）外围：调用递归函数。dfs(curLevel, curRoot);

    // 3）返回后果 resList。return resList;
}

四 资源分享 & 更多

1 历史文章 – 总览

2 博主简介

码农三少，一个致力于编写 极简、但齐全题解（算法 ）的博主。
专一于 一题多解、结构化思维，欢送一起刷穿 LeetCode ~

退出移动版