零 标题：算法（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 历史文章 - 总览
历史文章 - 总览
历史文章 - 总览
image.png
2 博主简介
码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专注于 一题多解、结构化思维 ，欢迎一起刷穿 LeetCode ~
