背景
写这篇文章次要是记录一下本人面试被问到的这个问题： 求二叉树每层最大值 到 结构一颗二叉树去验证 到进一步优化循环层数 的解答过程。(面试常见套路，手写 -> 优化 / 其余解法 / 工夫空间复杂度剖析)
工夫一久就会遗记怎么写，下次又得想半天，而面试必定不会让现场想半天的，所以须要熟记思路。
这个题目源于我写的字节跳动实习的面经 https://segmentfault.com/a/1190000038543869，将解答过程写进面经外面会比拟长，所以独自抽出来总结一下。
1. 求二叉树每层的最大节点
这个办法比拟常见，记得数据结构书中二叉树层序遍历的代码示例就是这个办法，leetcode 的题解也多是两层循环。
ps：如果一开始就写出一层循环那当然不会有后续让优化的问题了。但举荐写这种，后续大多会被问到怎么用一层实现 (我小米和字节都被问到了)。这时再装作想一想而后写进去岂不是更显得本人应变能力强，有算法根底而不是背进去的？
var largestValues = function(root) {if(!root) return []
const res = [] // 最终输入的后果，寄存每层的最大值
let queue = [root] // 根节点入队
while(queue.length) {
let len = queue.length
let tmp = [] // 寄存以后层的所有节点的值
while(len) { // 此处的 len 记录的是以后层的节点数，为 0 代表遍历完以后层的节点，开始遍历下一层
let curr = queue.shift()
if(curr.left) queue.push(curr.left)
if(curr.right) queue.push(curr.right)
tmp.push(curr.val)
len--
}
res.push(Math.max(...tmp))
}
return res
}2. 结构一颗二叉树, 用于验证咱们写的求每层最大值的函数
// 二叉树的节点的构造方法
function TreeNode(val, left, right) {
this.val = val
this.left = null
this.right = null
}
// 接下来咱们构建一颗第一层为 1，第二层为 2，3，第三层为 4，5，6 的二叉树
let p1 = new TreeNode(1)
let p2 = new TreeNode(2)
let p3 = new TreeNode(3)
let p4 = new TreeNode(4)
let p5 = new TreeNode(5)
let p6 = new TreeNode(6)
// 将这些节点相互连接起来
p1.left = p2
p1.right = p3
p2.left = p4
p2.right = p5
p3.left = p6
// 验证
console.log(largestValues(p1)); // 输入 [1, 3, 6]3. 循环层数优化：将刚刚写的求二叉树每层最大值的办法中的两层循环改为一层
思路：在后面的办法中，咱们内层循环的作用是记录以后层的节点数, 让咱们晓得什么时候本层节点遍历完。既然少了一层循环，那咱们就只能用额定空间去记录下一层节点了
var largestValuesImprove = function(root) {if(!root) return []
const res = [] // 最终输入的后果，寄存每层的最大值
let queue = [root] // 寄存以后层的节点
let nextLevel = [] // 寄存下一层的节点
let tmp = []
while(queue.length>0 || nextLevel.length>0) {if(queue.length===0) { // 以后层遍历完
queue = nextLevel // 取下一层
nextLevel = []
res.push(Math.max(...tmp))
tmp = []}
let curr = queue.shift()
tmp.push(curr.val)
if(curr.left) nextLevel.push(curr.left)
if(curr.right) nextLevel.push(curr.right)
}
// 这里肯定要留神最初一次跳出循环时没有走 if 语句，须要再把最初一层的值放入 res
res.push(Math.max(...tmp))
return res
}
// 验证
console.log(largestValuesImprove(p1));残缺代码
// 1. 求二叉树每层的最大节点
var largestValues = function(root) {if(!root) return []
const res = [] // 最终输入的后果，寄存每层的最大值
let queue = [root] // 根节点入队
while(queue.length) {
let len = queue.length
let tmp = [] // 寄存以后层的所有节点的值
while(len) { // 此处的 len 记录的是以后层的节点数，为 0 代表遍历完以后层的节点，开始遍历下一层
let curr = queue.shift()
if(curr.left) queue.push(curr.left)
if(curr.right) queue.push(curr.right)
tmp.push(curr.val)
len--
}
res.push(Math.max(...tmp))
}
return res
}
// 2. 结构一颗二叉树, 用于验证咱们写的求每层最大值的函数
function TreeNode(val, left, right) { // 节点的构造方法
this.val = val
this.left = null
this.right = null
}
// 接下来咱们构建一颗第一层为 1，第二层为 2，3，第三层为 4，5，6 的二叉树
let p1 = new TreeNode(1)
let p2 = new TreeNode(2)
let p3 = new TreeNode(3)
let p4 = new TreeNode(4)
let p5 = new TreeNode(5)
let p6 = new TreeNode(6)
// 将这些节点相互连接起来
p1.left = p2
p1.right = p3
p2.left = p4
p2.right = p5
p3.left = p6
// 3. 验证
console.log(largestValues(p1)); // 输入 [1, 3, 6]
// 4. 循环层数优化：将咱们刚刚写求二叉树每层的最大值中两层循环改为一层
// 思路：在后面的办法中，咱们内层循环的作用是记录以后层的节点数, 让咱们晓得什么时候本层节点遍历完。// 既然少了一层循环，那咱们就只能用额定空间去记录下一层节点了
var largestValuesImprove = function(root) {if(!root) return []
const res = [] // 最终输入的后果，寄存每层的最大值
let queue = [root] // 寄存以后层的节点
let nextLevel = [] // 寄存下一层的节点
let tmp = []
while(queue.length>0 || nextLevel.length>0) {if(queue.length===0) { // 以后层遍历完
queue = nextLevel // 取下一层
nextLevel = []
res.push(Math.max(...tmp))
tmp = []}
let curr = queue.shift()
tmp.push(curr.val)
if(curr.left) nextLevel.push(curr.left)
if(curr.right) nextLevel.push(curr.right)
}
// 这里肯定要留神最初一次跳出循环时没有走 if 语句，须要再把最初一层的值放入 res
res.push(Math.max(...tmp))
return res
}
console.log(largestValuesImprove(p1));