47道 LeetCode 题解带你搞懂二叉树（二）
本文为LeetCode题解二叉树的第二篇，主要包括二叉树属性相关的LeetCode题解。其他两篇可以在公众号主页查看！
1. 二叉树的完全性校验
给定一个二叉树，确定它是否是一个完全二叉树。百度百科中对完全二叉树的定义如下：
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2 个节点。）
示例 1：
输入：[1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
示例 2：
输入：[1,2,3,4,5,null,7]
输出：false
解释：值为 7 的结点没有尽可能靠向左侧。
提示： 树中将会有 1 到 100 个结点。
对于这道题目，我们可以使用层序遍历来解决。在层序遍历的过程中，需要用一个index来维护节点的索引，如果一个节点的index，那它的左孩子的索引是index * 2，右孩子的索引是index * 2 + 1。
这里我们初始化一个队列，用来存储当前节点node和当前节点的索引值index。使用一个count来记录当前已经遍历到第几个节点。如果当前节点的索引值index和count + 1相等，那么说明当前节点的位置时正确的，就继续遍历，如果不相等，说明中间缺少了节点，直接返回false，结束遍历。**
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isCompleteTree = function(root) {
if(!root){
return true
}
let count = 0
const queue = [{ node: root, index: 1 }]
while(queue.length){
const temp = queue.shift()
const node = temp.node
const index = temp.index
// 判断当前节点是否是正确的顺序值
if(index !== ++count){
return false
}
// 遍历当前节点的左右子树
node.left && queue.push({node: node.left, index: index * 2})
node.right && queue.push({node: node.right, index: index * 2 + 1})
}
return true
};
复杂度分析：
时间复杂度：O(n)，这里最坏的情况就是我们需要遍历整棵二叉树，所以时间复杂度为O(n)，其中n是二叉树的节点数； 空间复杂度：O(1)，我们需要初始化一个队列来保存当前遍历的节点，这个队列是一个常数空间，所以空间复杂度为O(1)。
2. 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1：
输入：[1,2,3]
1
/ \
2 3
输出：6
示例 2：
输入：[-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出：42
对于这道题目，我们可以使用递归遍历二叉树，我们需要的是最大的路径和，所以某个节点左右子树路径和和这个节点的值的和的最大值就是我们要求的解。
需要注意：
一条从父节点延伸下来的路径，只能进入左子树或者右子树，不能同时进入左右子树。 只有在最大贡献值大于 0 时，才会选取对应子节点。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
let sum = Number.MIN_SAFE_INTEGER
const dfs = (root) => {
if(!root){
return 0
}
// 计算左右子树的最大路径和
const left = dfs(root.left)
const right = dfs(root.right)
// 计算总的最大路径和
const maxSum = left + root.val + right
sum = Math.max(sum, maxSum)
// 返回当前计算出的最大路径
const max = root.val + Math.max(left, right)
return max < 0 ? 0 : max
}
dfs(root)
return sum
};
复杂度分析：
时间复杂度： O(N)，其中 N 是二叉树中的节点个数。对每个节点访问不超过 2 次。 空间复杂度： O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。
3. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。示例：给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
遇到二叉树的问题，我们在遍历时通常是采用深度优先遍历和广度优先遍历，这里需要求直径，我们就使用到了深度优先遍历。
从根节点进行遍历，在遍历到每个节点的时候，将其左右子树的最大深度加在一起，与结果res对比，并将最大的值赋值给热搜，这样使res一直保持是最大的值。最后返回res即可。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var diameterOfBinaryTree = function(root) {
let res = 0
function depth(rootNode){
if(!rootNode) return 0
let l = depth(rootNode.left) // l为左子树的深度
let r = depth(rootNode.right) // r为右子树的深度
res = Math.max(res, l + r) // 计算最大直径l+r，更新res，能保持其一直是最大值
return Math.max(l ,r) + 1 // 返回以该节点为根的子树的深度
}
depth(root)
return res
};
复杂度分析：
时间复杂度：O(n)，其中n为二叉树的节点数，这里需要遍历整棵二叉树，所以时间复杂度为O(n)。 空间复杂度：O(h)，其中h是二叉树的最大深度，是一个常数变量。
4. 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。说明: 叶子节点是指没有子节点的节点。示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
这个题目就是对二叉树数进行深度优先遍历，在遍历的过程中将当前节点的值存储在字符串中，直到没有子节点，就将这个遍历出的结果字符串存入结果数组中。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {string[]}
*/
var binaryTreePaths = function(root) {
if(!root) return []
let res = []
const buildPath = (root, resStr) => {
if(!root.left && !root.right){
resStr += root.val
res.push(resStr)
return
}
resStr += root.val + '->'
if(root.left){
buildPath(root.left, resStr)
}
if(root.right){
buildPath(root.right, resStr)
}
}
buildPath(root, '')
return res
};
复杂度分析
时间复杂度：O(N)，其中 N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)，故时间复杂度为 O(N)； 空间复杂度：O(N)，其中 N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 N，此时每一层的 path 变量的空间代价的总和的空间复杂度为 O(N)，最好情况下，当二叉树为平衡二叉树时，它的高度为 logN，此时空间复杂度为O((logN)2)。
5. 对称的二叉树
给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:5r
1
/ \
2 2
\ \
3 3
进阶： 你可以运用递归和迭代两种方法解决这个问题吗？
递归的思路比较简单，具体实现思路如下：
首先判断当前树是否为空，空则直接返回true，否则就左子树的左子树和右子树的右子树是否相等 如果左节点或者右节点为空时，就比较对应的右节点或左节点是否为空，为空则返回true，否则就返回false 如果左右节点都不为空，就判断左节点的左节点和右节点的右节点是否相等 如果相等，就传入该节点的子节点进行递归，否则就返回false
迭代方法需要借助队列来实现，具体实现思路如下：通过「同步移动」两个指针的方法来遍历这棵树，l 指针和 r 指针一开始都指向这棵树的根，随后 l 右移时，r 左移，l 左移时，r 右移。每次检查当前 l 和 r 节点的值是否相等，如果相等再判断左右子树是否对称。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
// 迭代的实现
const isSymmetric = (root) => {
if (!root) return true
let queue = [root.left, root.right]
while (queue.length > 0) {
let node1 = queue.shift(), node2 = queue.shift()
if (node1 === null && node2 === null) continue
if (node1 === null || node2 === null || node1.val !== node2.val) return false
queue.push(node1.left, node2.right, node1.right, node2.left)
}
return true
}
// 递归的实现
var isSymmetric = function(root) {
if(!root){
return true
}
return isSameTree(root.left, root.right)
};
const isSameTree = (l, r) => {
if(!l) return r === null
if(!r) return l === null
if(l.val !== r.val) return false
return isSameTree(l.left, r.right,) && isSameTree(l.right, r.left)
}
递归实现的复杂度分析：
时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)，其中n是这棵树的节点数。 空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。
迭代实现的复杂度分析：
时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)，其中n是这棵树的节点数。 空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。
6. 二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。示例 1：
输入：
3
/ \
9 20
/ \
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
提示：节点值的范围在32位有符号整数范围内。
这是一道比较简单的题目，就是二叉树的层序遍历。这里使用BFS（广度优先遍历），在遍历的过程中，将每层的节点值保存在队列中，然后将所有值出栈并相加。除以当前层的队列的长度就是这一层的平均值。将其放入结果中。重复上述步骤，直到遍历完整棵二叉树，返回最后的结果。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var averageOfLevels = function(root) {
if(!root){
return []
}
const res = []
const queue = []
queue.push(root)
while(queue.length){
const len = queue.length
let sum = 0
for(let i = 0; i < len; i++){
const cur = queue.shift()
sum += cur.val
if(cur.left){
queue.push(cur.left)
}
if(cur.right){
queue.push(cur.right)
}
}
res.push(sum / len)
}
return res
};
复杂度分析：
时间复杂度：O(n)，其中 n 是二叉树中的节点个数。广度优先搜索需要对每个节点访问一次，时间复杂度是 O(n)。需要对二叉树的每一层计算平均值，时间复杂度是 O(h)，其中 h 是二叉树的高度，任何情况下都满足h≤n。因此总时间复杂度是 O(n)。 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。
7. 二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
对于二叉树的题目，最常用的方法就是深度优先遍历（DFS）和广度优先遍历（BFS）。下面就来用这两种方法来解决这个问题。
DFS：
设置一个level，来保存当前遍历的二叉树的层级，初始值为0 由于我们需要返回的是右视图的节点值，所以先遍历右节点的值，将右节点保存在结果数组中 然后遍历左节点 当结果数组的长度和二叉树当前的层级相同时，就将当前的节点值保存 重复上述步骤，直至遍历完二叉树的所有节点
BFS：
使用广度优先遍历来遍历二叉树，这就相当于二叉树的层序遍历，对于每一层的遍历结果，取最后一个即可，这里我们使用队列来处理。
初始化一个队列，将根节点加入到队列中 当队列不为空的时候，就将队列的元素出队，将最后一个元素加入到结果数组中 在元素出队列的时候，将元素的左右子节点分别加入到队列中 重复上面的第二三步，直至队列为空**
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// DFS的实现：
var rightSideView = function(root) {
if(!root) return []
let res = []
dfs(root, 0, res)
return res
};
function dfs(root, level, res){
if(root){
if(res.length === level){
res.push(root.val)
}
dfs(root.right, level+1, res)
dfs(root.left, level+1, res)
}
}
// BFS的实现：
var rightSideView = function(root) {
if(!root) return []
let res = []
let queue = [root]
while(queue.length > 0){
let len = queue.length
while(len){
let node = queue.shift()
if(len === 1){
res.push(node.val)
}
if(node.left){
queue.push(node.left)
}
if(node.right){
queue.push(node.right)
}
len--
}
}
return res
};
DFS复杂度分析：
时间复杂度 : O(n)。其中n是二叉树的节点数，深度优先搜索最多访问每个结点一次，因此是线性复杂度。 空间复杂度 : O(n)。其中n是二叉树的节点数，最坏情况下，栈内会包含接近树高度的结点数量，占用 O(n) 的空间。
BFS复杂度分析：
时间复杂度 : O(n)。其中n是二叉树的节点数，每个节点最多进队列一次，出队列一次，因此广度优先搜索的复杂度为线性。 空间复杂度 : O(n)。其中n是二叉树的节点数，每个节点最多进队列一次，所以队列长度最大不不超过 n，所以这里的空间代价为 O(n)。
8. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
树中节点的数目范围是 [0, 5 * 10]0 <= Node.val <= 5 * 10题目数据保证输入的树是 完全二叉树
进阶： 遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
对于这道题目，我们可以使用深度优先遍历或者广度优先遍历来计算二叉树的节点数。
（1）深度优先遍历：
深度优先遍历就很简单了，题中传入的是二叉树，需要返回的是二叉树，所以可以直接进行递归计算二叉树的节点数：
如果子树为空节点数为 0 如果子树存在左子树或右子树则节点数+1，继续递归分别求左子树节点数和右子树节点数
复杂度分析：
时间复杂度：O(n)，其中n是二叉树的节点数，我们需要遍历一遍整个二叉树； 空间复杂度：O(h)，其中h是二叉树的高度，递归的时间复杂度为O(h)。
（2）广度优先遍历：
广度优先遍历往往是初始化一个对来保存当前层的节点，在对当前层的节点进行操作。对于这题目，我们只需要在节点进入队列的时候，结果加一即可。
复杂度分析：
时间复杂度：O(n)，其中n是二叉树的节点数，我们需要遍历一遍整个二叉树； 空间复杂度：O(n)，其中n是队列的长度，我们需要将每一层都放在队列中。
（3）二分法上面的两种方法的时间复杂度都是O(n)，下面用二分法来解决，时间复杂度会降低。
我们知道，对于一个完全二叉树，它的所有子树都是完全二叉树，有的子树是满二叉树，满二叉树的的节点个数计算公式如下：2-1，其中h为当前树的高度。
那什么情况下就是满二叉树呢，我们知道，二叉树中有个树的深度的概念，指的就是根节点到这个节点所经历的边的个数， 所以我们只需要判断左右子树的高度手否相等来判断当前树是不是满二叉树。
如果不是满二叉树，那就是规模小一点的完全二叉树，就进行递归处理。
复杂度分析：
时间复杂度：每次递归调用对应了一层树高，调用logN次，每次调用计算完全二叉树的高度需要O(logN)，所以时间复杂度为O(logN) 空间复杂度：O(1)，我们只需要维护有限的额外空间。
广度优先遍历：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var countNodes = function(root) {
if(!root){
return 0
}
let queue = [root]
let res = 1
while(queue.length){
let node = queue.shift()
if(node.left){
queue.push(node.left)
res++
}
if(node.right){
queue.push(node.right)
res++
}
}
return res
};
深度优先遍历：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var countNodes = function(root) {
if(!root){
return 0
}
return 1 + countNodes(root.left) + countNodes(root.right)
}
二分法：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var countNodes = function(root) {
if(!root){
return 0
}
let leftHeight = 0, rightHeight = 0
let leftNode = root, rightNode = root
while(leftNode){
leftHeight++
leftNode = leftNode.left
}
while(rightNode){
rightHeight++
rightNode = rightNode.right
}
if(leftHeight === rightHeight){
return 2 ** leftHeight - 1
}
return 1 + countNodes(root.left) + countNodes(root.right)
};
9. 左叶子之和
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
对于这道题目，我们可以对二叉树进行层序遍历， 初始化一个对来queue来保存当前层的元素，遍历队列中的元素，如果该节点的左子树不存在左右子树，说明它是一个左叶子节点，将其加在结果上。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var sumOfLeftLeaves = function(root) {
if(!root) return 0
let res = 0
const queue = [root]
while(queue.length){
const cur = queue.shift()
if(cur.left){
if(!cur.left.left && !cur.left.right){
res += cur.left.val
}
queue.push(cur.left)
}
if(cur.right){
queue.push(cur.right)
}
}
return res
};
复杂度分析：
时间复杂度：O(n)，最坏的情况下，也就是二叉树只有右子树，而形成一个链表的时候，我们需要遍历完整个二叉树，时间复杂度就是 O(n)； 空间复杂度：O(n)，其中n表示队列的长度，这个长度永远小于等于二叉树的节点的数量。
10. 找树左下角的值
给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:
输入:
2
/ \
1 3
输出:1
示例 2:
输入:
1
/ \
2 3
/ / \
4 5 6
/
7
输出:7
注意: 您可以假设树（即给定的根节点）不为 NULL。
这里可以对二叉树进行层序遍历，而层序遍历就是基于广度优先遍历的。
在遍历的过程中，我们初始化一个队列来保存当前层的节点，这个过程中，需要先将根节点的右子节点加入到队列中，再将其左子节点加入到队列中。
这个过程中，将对列元素出队，并加入到res数组中，这样数组的最后一个值就是二叉树左下角的值。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var findBottomLeftValue = function(root) {
const queue = [root]
let res = []
while(queue.length){
const node = queue.shift()
res.push(node.val)
node.right && queue.push(node.right)
node.left && queue.push(node.left)
}
return res[res.length - 1]
};
复杂度分析：
时间复杂度：O(n)，其中n是二叉树的节点数，我们需要遍历整棵树； 空间复杂度：O(n)，其中n是二叉树的高度，我们需要初始化一个数组来保存二叉树的所有节点；
11. 最大二叉树
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
二叉树的根是数组 nums中的最大元素。左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树。
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
示例 2：
输入：nums = [3,2,1]
输出：[3,null,2,null,1]
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000nums中的所有整数 互不相同
这道题目我们直接使用递归来实现：
首先获取到数组中最大的值，来作为当前的根节点 分别获取数组中最大值的左边的数组元素和右边的数组元素 使用两个数组分别进行递归构建二叉树的左右子树
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var constructMaximumBinaryTree = function(nums) {
if(nums.length === 0){
return null
}
let max = Math.max(...nums)
let root = new TreeNode(max)
let leftArray = nums.slice(0, nums.indexOf(max))
let rightArray = nums.slice(nums.indexOf(max) + 1)
root.left = constructMaximumBinaryTree(leftArray)
root.right = constructMaximumBinaryTree(rightArray)
return root
};
复杂度分析：
时间复杂度：O(n)，一共递归了 n 次。每次递归寻找根节点时，需要遍历当前索引范围内所有元素找出最大值。一般情况下，每次遍历的复杂度为 O(logn)，总复杂度为 O(nlogn)。最坏的情况下，数组 nums 有序，总的复杂度为 O(n) 空间复杂度：O(n)。递归调用深度为 n。平均情况下，长度为 n 的数组递归调用深度为 O(logn)。
12. 相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
我们只需要进行递归遍历两个树对应的节点，看看是否一致，一致的话就直接返回false。这里使用的是深度优先遍历来进行遍历操作。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
if(!p && !q){
return true
}
if(p === null || q === null){
return false
}
if(p.val !== q.val){
return false
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};
复杂度分析：
时间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。
13. 出现次数最多的子树元素和
给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
示例 1：
输入:
5
/ \
2 -3
返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。
示例 2：
输入：
5
/ \
2 -5
返回 [2]，只有 2 出现两次，-5 只出现 1 次。
提示： 假设任意子树元素和均可以用 32 位有符号整数表示。
这道题和二叉树的众数那道题是一样的思路：
首先，先遍历出一次树， 求所有节点的子树和 在遍历的过程中，使用map来记录每个元素出现的次数 遍历完成之后，遍历map，找出次数最多的和，放在res中即可
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var findFrequentTreeSum = function(root) {
let map = {}, res = [], max = 0
const calcuSum = (root) => {
if(!root){
return 0
}
let left = calcuSum(root.left)
let right = calcuSum(root.right)
let sum = left + right + root.val
// 将当前节点赋值为其所有子节点的和，方便后面进行计算
root.val = sum
map[sum] ? map[sum] += 1 : map[sum] = 1
return root.val
}
calcuSum(root)
for(let key in map){
if(map[key] === max){
res.push(key)
}
if(map[key] > max){
max = map[key]
res = [key]
}
}
return res
};
复杂度分析：
时间复杂度：O(n)，其中n是这棵树的节点数量，我们需要遍历整棵树，来求每个节点的子树和。 空间复杂度：O(n)，其中n是这棵树的节点数量，这里需要的是递归的栈空间的空间代价。
14. 二叉树最大宽度
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree） 结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。**示例 1:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
示例 2:
输入:
1
/
3
/ \
5 3
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 3:
输入:
1
/ \
3 2
/
5
输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
示例 4：
输入:
1
/ \
3 2
/ \
5 9
/ \
6 7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。
这个题目，我们可以一层一层对二叉树进行遍历，初始化一个队列来保存这一层的节点，这个队列中保存着当前节点的节点值和索引值。
我们知道，一个节点的左子树的索引值是其索引值的两倍，即：left = index* 2，右子树的索引值是其索引值的两倍加一，即：right = index * 2 + 1。所以每层的宽度就是：right - left + 1，这样每一层的宽度值就求出来了，最大值也就自然而然的求出来了。
除此之外，我们还要考虑一种情况，就是二叉树深度特别深的时候，索引有可能就超出了数字的有效值。题目最后标明了：答案在32位有符号整数的表示范围内。也就是说最终答案那个最大宽度是不会超过32位有符号整数的。上面的想法是空节点也标注了索引，假如层数很多，但每层只有一个右节点的用例，空节点也计数就不行了，因为并没有限制层数。我们可以让同一层节点的索引先减去此层第一个节点的索引再来计算子节点的索引，这样每一层的索引都是从0开始的，从而解决数字大的问题。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var widthOfBinaryTree = function(root) {
if(!root){
return 0
}
const nodes = [{node: root, index: 0}]
let res = 0
while(nodes.length){
let len = nodes.length
const start = nodes[0].index
const end = nodes[len - 1].index
res = Math.max(res, end - start + 1)
while(len--){
let {node, index} = nodes.shift()
index -= start
node.left && nodes.push({ node: node.left, index: index * 2 })
node.right && nodes.push({ node: node.right, index: index * 2 + 1 })
}
}
return res
};
复杂度分析：
时间复杂度：O(n)，其中n是二叉树的节点数，我们需要遍历完整个二叉树； 空间复杂度：O(n)，其中n是nodes栈的长度。
15. 二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
递归实现：递归二叉树的节点，获取左子树和右子树的最大深度，比较后，返回最大深度，具体步骤如下：
判断二叉树是否为空，空的直接返回 0，结束，非空二叉树继续 分别递归计算左右子树的最大深度 根据返回两者的两者数字，比较后的返回二叉树的最大深度
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if(!root){
return 0;
}else{
var leftDepth = maxDepth(root.left)
var rightDepth = maxDepth(root.right)
return Math.max(leftDepth,rightDepth)+1
}
};
复杂度分析：
时间复杂度： O(n)：通过递归的方式查询了树的所有子节点。查询花费 O(n) 的时间。 空间复杂度： O(n)：每次递归都需要创建新的临时空间，空间复杂度 O(n)。
16. 二叉树的最小深度
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
树中节点数的范围在 [0, 10]内-1000 <= Node.val <= 1000
层序遍历实现：
设置一个level，表示当前的层数，然后对二叉树进行层序遍历，每增加一层，level就加一，直到某个节点没有左右子树，结束遍历，返回level。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
if(!root){
return 0;
}
var level = 0;
var queue = [root];
while(queue.length){
level += 1;
var len = queue.length;
while(len--){
var node = queue.shift();
if (!node.left&&!node.right){
return level;
}
if(node.left){
queue.push(node.left);
}
if(node.right){
queue.push(node.right);
}
}
}
return level;
};
复杂度分析：
时间复杂度：O(n)，其中 n 是树的节点数。对每个节点访问一次。 空间复杂度：O(n)，其中 n 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。
17. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
复杂度分析：
树中的节点数在范围 [0, 5000] 内 -10<= Node.val <= 10