跟着灵茶山艾府大佬学习算法思路的day9，目标是在一个月内掌握hot100
b站链接如下：
二叉树的层序遍历 题目描述：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
1
2
输入：root = [1]
输出：[[1]]
示例 3：
1
2
输入：root = []
输出：[]
思路：
最基本的思路其实没啥好说的，就是用队列逐步入队下层节点就行，但在具体的实现上有些说道。我们可以考虑在一个数组上，在将遍历到的节点放入一个临时数组以记录到答案中的同时，以队列方式一直推入在遍历的节点的左右节点来保证循环，但这种方法使用的shift()会一直带来数组的队首元素删除，效率上是不佳的。而灵神的做法通过cur和nxt数组来分层，在处理cur当前层的同时用nxt收集下一层，就避免了shift()的o(n)尴尬。
代码：
shift()方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var levelOrder = function(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
const currentLevel = []; // 用以临时记录当前遍历的层的所有节点
// 根据queue当前数量，处理当前层的所有节点
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
// 将子节点加入队列
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
};
灵神的方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var levelOrder = function(root) {
if (root === null) {
return [];
}
const ans = [];
let cur = [root];
while (cur.length) {
const nxt = [];
const vals = [];
for (const node of cur) {
vals.push(node.val);
if (node.left) nxt.push(node.left);
if (node.right) nxt.push(node.right);
}
cur = nxt;
ans.push(vals);
}
return ans;
};
总结：
其实shift的劣势是显而易见的，不需要太多分析，认真分析的原因是我一开始是这么做的，现在再看显得有些笨比。
不过值得一提的是，在力扣的小规模测试数据上，shift方法的效果甚至还能优一些些，一方面是数据量太少，没进入shift的劣势拐点，另一方面每次都新建一个nxt数组的空间创建开销也是比较明显的。
上为双数组，下为shift。
二叉树的锯齿形层序遍历 题目描述：
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：
1
2
输入：root = [1]
输出：[[1]]
示例 3：
1
2
输入：root = []
输出：[]
思路：
思路还是之前的思路，只是在偶数层时我们翻转一下，因为需要返回的数组本身就是二维数组，是带有目前已遍历的层的信息的，我们自然也能够知道接下来的一层是奇数层还是偶数层，所以根据ans的长度做翻转判断就好。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var zigzagLevelOrder = function(root) {
if (!root) return [];
const ans = [];
let cur = [root];
while (cur.length) {
const nxt = [];
const vals = [];
for (const node of cur) {
vals.push(node.val);
if (node.left) nxt.push(node.left);
if (node.right) nxt.push(node.right);
}
// ans.length % 2：0 意味着要推入的本层为奇数层，不反转
// 1 意味着要推入的是偶数层，反转
ans.push(ans.length % 2 ? vals.reverse() : vals);
cur = nxt;
}
return ans;
};
总结：
沿用灵神的层序设计思路，很简单的一个延伸。
找树左下角的值 题目描述：
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
1
2
输入: root = [2,1,3]
输出: 1
示例 2:
1
2
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
思路：
求最底层最左边有两个方法，一个是求层序遍历完成后，取出最后一层的第一个节点（可以直接层序完后，将return的结果改为[ans.length-1][0]，但这样的效率很低，应该减少节点操作数量）；一个是将原先从左到右的层序遍历改为从右到左，这样所求就是最后一个节点。
代码：
1
2
3
4
5
6
7
8
9
10
11
var findBottomLeftValue = function(root) {
const cur = [root];
let node = null;
while (cur.length) { // 空数组 [] 在 JS 中是真值，不能cur
node = cur.shift();
if (node.right) cur.push(node.right); // 先右
if (node.left) cur.push(node.left); // 后左
}
return node.val;
};
总结：
因为只需要求从右到左最后一个节点，所以对于结果的存储可以简洁一些，不需要存下整个遍历数组。