「题目：」
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。
「示例：」
输入：root = [3,9,20,null,null,15,7]，输出：[[3],[9,20],[15,7]]。
「递归解法：」
使用深度优先搜索来解决，递归的深度即是二叉树的层级，然后通过二维数组来记录当前层级的节点元素。
时间复杂度：O(n)，空间复杂度：O(n)。
const levelOrder = root => {
const ans = [];
dfs(root, 0, ans);
return ans;
}
function dfs(root, level, ans) {
if (!root) {
return;
}
if (!ans[level]) {
ans[level] = [];
}
ans[level].push(root.val);
dfs(root.left, level + 1, ans);
dfs(root.right, level + 1, ans);
return;
}
「迭代解法：」
使用广度优先搜索来解决，通过队列来保存每一层根节点的左右子树，再使用二位数组来存储每层的节点元素。
时间复杂度：O(n)，空间复杂度：O(n)。
const levelOrder = root => {
if (!root) {
return [];
}
const ans = [];
let queue = [root];
while (queue.length) {
const len = queue.length
const item = [];
for (let i = 0; i < len; i++) {
const currentRoot = queue.shift();
item.push(currentRoot.val);
currentRoot.left && queue.push(currentRoot.left);
currentRoot.right && queue.push(currentRoot.right);
}
ans.push(item);
}
return ans;
}
上述解题思路中，使用 shift 方法来完成出队的操作，该方法在 JavaScript 中非常的低效，原因在于：执行 shift 方法需要遍历一次数组，将每个元素向前平移。
可以通过数组下标访问 + 临时变量完成空间换时间的优化。
const levelOrder = root => {
if (!root) {
return [];
}
const ans = [];
let queue = [root];
while (queue.length) {
const len = queue.length;
const item = [];
const _queue = [];
for (let i = 0; i < len; i++) {
const currentRoot = queue[i];
item.push(currentRoot.val);
currentRoot.left && _queue.push(currentRoot.left);
currentRoot.right && _queue.push(currentRoot.right);
}
queue = _queue;
ans.push(item);
}
return ans;
}
107. 二叉树的层序遍历 II
「题目：」
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
「示例：」
输入：root = [3,9,20,null,null,15,7]，输出：[[15,7],[9,20],[3]]。
「解题思路：」
由于二叉树自身递归定义的特性，无法直接从底层开始遍历，那么本道题的解法就是在【102】解题思路的基础上，将得到的结果进行反转即可。
时间复杂度：O(n)，空间复杂度：O(n)。
const levelOrderBottom = root => {
const ans = [];
dfs(root, 0, ans);
ans.reverse();
return ans;
}
function dfs(root, level, ans) {
if (!root) {
return;
}
if (!ans[level]) {
ans[level] = [];
}
ans[level].push(root.val);
dfs(root.left, level + 1, ans);
dfs(root.right, level + 1, ans);
return;
}
044. 二叉树每层的最大值
「题目：」
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
「示例：」
输入: root = [1,3,2,5,3,null,9]，输出: [1,3,9]。
「解题思路：」
这是一道层级遍历的变题，回顾【102】的两种解法，只要在层级遍历的基础上，筛选出每层的最大值即可。
下面是递归的解法，感兴趣的同学可以尝试迭代的解法。
时间复杂度：O(n)，空间复杂度：O(n)。
const largestValues = (root) => {
const ans = [];
dfs(root, 0, ans);
return ans;
}
function dfs(root, level, ans) {
if (!root) {
return;
}
if (ans[level] === undefined) {
ans[level] = Number.MIN_SAFE_INTEGER;
}
ans[level] = Math.max(ans[level], root.val);
dfs(root.left, level + 1, ans);
dfs(root.right, level + 1, ans);
return;
}
45.二叉树最底层最左边的值
「题目：」
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
「示例：」
输入: root = [2,1,3]，输出: 1。
「解题思路：」
同样是一道层级遍历的变题，回顾递归的解法，在递归二叉树的过程中，始终都是按照自上而下，从左到右的顺序来寻找每层的元素。所以只需要记录每一层的第一个元素，即可找到最底层最左边的元素。
*并且可以通过维护当前取值的层次，将一维数组压缩成常量，从而将空间复杂度由 O(n) 优化为 O(1)*。
时间复杂度：O(n)，空间复杂度：O(1)。
const findBottomLeftValue = (root) => {
let ans = 0;
let currentLevel = -1;
const dfs = (root, level) => {
if (!root) {
return;
}
if (level > currentLevel) {
ans = root.val;
currentLevel = level;
}
dfs(root.left, level + 1);
dfs(root.right, level + 1);
}
dfs(root, 0);
return ans;
}
写在最后
LeetCode 数据结构篇根据难度划分为：
数据结构入门篇
数据结构进阶篇
数据结构高级进阶篇
每篇会根据题目的类型和解题思路形成不同的专题，这样更利于摸清本质，将技巧内化于心。
感兴趣的小伙伴可以关注下方的公众号，或者微信搜索“漫谈大前端”，如果本文对你有帮助，欢迎点赞、分享、转发。
相关链接：
https://leetcode.cn/problems/binary-tree-level-order-traversal/
https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
https://leetcode.cn/problems/hPov7L/
https://leetcode.cn/problems/LwUNpT/
