零 题目：算法（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 ~