乐趣区

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

零 题目:算法(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 ~

退出移动版