网络日志

103、二叉树的锯齿形层序遍历 | 算法(leetcode,附思维导图 + 全部解法)300题

零 标题:算法(leetcode,附思维导图 + 全部解法)300题之(103)二叉树的锯齿形层序遍历

一 题目描述

二 解法总览(思维导图)

三 全部解法

1 方案1

1)代码:

// 方案1: “自己。层序遍历法”。

// 思路:
// 1)边界:若 root 为null,则 直接返回 [] 。
// 2)状态初始化:q1 = [root], q2 = [], resList = [], level = 0 。
// 3)遍历:条件为 队列 q1 不为空 。
// 4)返回结果:resList 里,下标为奇数的 元素项(数组形式)进行翻转。
// resList.map((item, level) => level%2 === 1 ? item.reverse() : item);
var zigzagLevelOrder = function(root) {
    // 1)边界:若 root 为null,则 直接返回 [] 。
    if(root === null){
        return [];
    }

    // 2)状态初始化:q1 = [root], q2 = [], resList = [], level = 0 。
    let q1 = [root],
        q2 = [],
        resList = [],
        level = 0;
    
    // 3)遍历:条件为 队列 q1 不为空 。
    while(q1.length !== 0){
        let temp = q1.shift();
        if(temp.left !== null){
            q2.push(temp.left);
        }
        if(temp.right !== null){
            q2.push(temp.right);
        }
        if(resList[level] === undefined){
            resList[level] = [];
        }
        resList[level].push(temp.val);
        if(q1.length === 0){
            q1 = q2;
            q2 = [];
            level++;
        }
    }

    // 4)返回结果:resList 里,下标为奇数的 元素项(数组形式)进行翻转。
    // resList.map((item, level) => level%2 === 1 ? item.reverse() : item);
    return resList.map((item, level) => level%2 === 1 ? item.reverse() : item);
};

2 方案2

1)代码:

// 方案2 “递归法(自己)”。
// 技巧:“一般来说,二叉树优先考虑使用递归,递归的形参情况根据问题等进行定义即可”。

// 思路:
// 1)状态初始化:curLevel = 0, curRoot = root, resList = [] 。
// 2)调用自定义的递归函数。
// 3)返回结果 resList 。
var zigzagLevelOrder = function(root) {
    // 递归实现
    const dfs = (curLevel = 0, curRoot = null) => {
        // 1)递归出口
        if (!curRoot) {
            return;
        }

        // 2)递归主体
        // 2.1)若 当前层没有被初始化,则 resList[curLevel] = [] 。
        if (!resList[curLevel]) {
            resList[curLevel] = [];
        }

        const {left, right, val} = curRoot;
        // 2.2)若 当前层为奇数,则 相应数组进行 “倒插” —— resList[curLevel].unshift(val) 。
        if ((curLevel % 2) === 1) {
            resList[curLevel].unshift(val);
        }
        // 2.3)若 当前层为偶数,则 相应数组进行 “顺插” —— resList[curLevel].push(val) 。
        else {
            resList[curLevel].push(val);
        }

        // 2.4)当前层次 + 1 并 对左子树进行递归处理。
        dfs(curLevel + 1, left);
        // 2.4)当前层次 + 1 并 对右子树进行递归处理。
        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 ~