二叉树的深度算法是二叉树中比较基础的算法。 回答LeetCode第104题。
而且可以看出，在LeetCode之后，存在第110题、第543题等需要对该算法进行变形的算法问题。 如果知道二叉树深度算法的递归过程，就可以很容易地制作这两个问题。
关于二叉树的相关知识，可以看到我的这篇报道： (数据结构)树的简要分析总结(安装js ) ) ) ) ) )。
主题给定二叉树，说明找出其最大深度。
二叉树的深度是从根节点到最远的叶节点的最长路径上的节点数。
说明：叶节点是指没有子节点的节点。
例如：给定二叉树[ 3，9，20，null，null，15，7 ]，
3/ 9 20/ 15 7返回其最大深度3。 请注意，复制代码的此二叉树存储在链式存储法中，而不是数组中。
1 .在解决什么是递归问题之前，先了解一下什么是递归吧。 如果你已经掌握了，直接跳过这个。
那么朗(wang )朗诵(ba )教科书(nian )内容(jing )开始。
递归分为“传递”和“回去”。 “给”是传达，“回去”是执行一个函数解决了一个子问题。 递归的实现是通过不断地将问题分解为子问题，解决子问题，最终解决原问题。
递归的核心在于递归公式，分析递归公式后，递归问题也能得到实际解决。 递归是一种广泛使用的编程技术，在很多地方都有使用，如深度快速遍历(本题使用它)、二叉树的前中后序遍历等。
递归必须满足以下三个条件：
可分解为多个子问题； 子问题不仅数据规模不同，求解思路不变； 有递归结束条件。 递归的特点是代码简洁。 在很多情况下，很难理解递归的每个过程。 因为不符合人类的思维习惯，但实际上没有必要理解。 b和c解决后，只要可以导出a即可，无需考虑b和c是如何在子问题中解决的。 (请参阅。
其次，如果递归太深，内存可能会耗尽。 递归时会保存很多调用记录，因此会保留调用堆栈。 如果堆栈太大而超出可用内存空间，则会发生内存溢出。 我们将其称为堆栈溢出。 解决方案有以下4种。
递归调用超过一定深度之后，直接报错，不再递归下去。深度会溢出多少并不通过计算知道。 另外，即使报告了错误，程序也会停止运行，所以这个方案确实可以防止内存溢出，但似乎没什么用。缓存重复计算。递归可能会重复调用已经求解的f(k )的结果。 在这种情况下，缓存f ) k )并使用哈希表进行缓存是常见的(在js中可以通过对象实现)。 第二次执行f(k )时，只需直接从缓存中获取即可。改为非递归代码。实际上被变更为循环的写法。 修正后的循环表示法本质上也是递归，只是手动实现了递归堆栈。 循环编写方法的代码实现比递归复杂，也不够优雅。 3358www.Sina.com/使用的是尾递归。的技术，需要验证运行时环境是否提供了此优化。 如果支持尾部调用优化，则如果函数a的尾调用优化调用另一个函数b，当它进入b时，将不会保留a的调用记录(例如，某些a的内部变量)，因此长调用栈说到递归，必须提到递归的经典主题。 那是“爬楼梯问题”，应对LeetCode第70题。
最后一步是：假设您正在爬楼梯。 到达屋顶需要n (正整数)步。 每次都能爬一段或两段。 爬屋顶的方法有几种？
首先，请列出n=1，n=2.的走法，试着找出规律。
楼梯步行法总数11121、22312、111、213到这里可以找到几个规律。 那就是，走到第3段的方法是2段和1段之和。 为什么会这样呢？ 我们要通过现象发现本质。 本质上，走到第n级，要么先走到第n-1级，再上一级楼梯，要么走到第n - 2级，再上两级。
因此，得到f(n )=f(n-1 ) f ) n-2 )的递推公式
递归格式：
varclimbstairs=function(n ) { let map={}； functionf(n ) if ) n3 )返回n； if(map(n ) ) returnmap )； letr=f(n-1 ) f ) n-2； map[n]=r； 返回r； }returnf(n )复制代码是因为f(n )=f(n-1 ) f ) n-2 )。 这里的f(n-1 )还可以从f ) n-2 ) f ) n-3 )中得到。 这里的f(n-2 )
) 被执行了两次，所以就需要缓存 f(n-2) 的结果到 map 对象中，来减少运算时间。循环写法：
var climbStairs = function(n) { if (n < 3) return n; let step1 = 1, // 上上一步 step2 = 2; // 上一步 let tmp; for (let i = 3; i <= n; i++) { tmp = step2; step2 = step1 + step2; step1 = tmp; } return step2;};复制代码 2. 问题分析说完递归后，我们就来分析题目吧。
首先我们试着找出递归规律。首先我们知道，除了叶子节点，二叉树的所有节点都有会有左右子树。那么如果我们知道左右子树的深度，找出二者之间的最大值，然后再加一，不就是这个二叉树的深度吗？其次以 叶子节点 为根节点的二叉树的高度是 1，我们就可以根据通过这个作为递归的结束条件。
3. 代码实现 /** * 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) { function f(node) { if (!node) return 0; return Math.max(f(node.left), f(node.right)) + 1; } return f(root);};复制代码这里用到了深度优先遍历，会沿着二叉树从根节点往叶子节点走。另外，因为没有重复计算，所以不需要对结果进行缓存。还有就是，因为没有多余的变量要保存，可以直接把 maxDepth 函数写成递归函数。
4. 扩展：数组存储的二叉树如何求深度？关于如何用数组存储（顺序存储法）的二叉树，这里就不提了，请看我前面提到的相关文章。
求一个数组表示的二叉树的深度，可以看作求 对应的完全二叉树的深度。
在此之前，我们先看看如何求出一个节点个数为 n 的 满二叉树 的深度 k。
深度 k个数 n1123 (=1+2)37 (=1+2+4)415 (=1+2+4+8)规律很明显，通过等比数列求和公式化简，我们得到 k = Math.log2(n+1)，其中 k 为深度，n 为满二叉树的节点个数。那么对于一个完全二叉树来说，将 k 向上取整即可：k = Math.ceil( Math.log2(n+1) )。
所以对于一个顺序存储法存储的长度为 n 的二叉树，其高度 k 为：
k = Math.ceil( Math.log2(n+1) )复制代码（需要注意的是，这里的数组是从 0 开始存储节点的。）
参考 可爱的小懒虫的网络日志——尾调用优化数据结构与算法之美：10 | 递归：如何用三行代码找到“最终推荐人”？