【算法题】递归求二叉树深度

二叉树的深度算法，是二叉树中比较基础的算法了。对应LeetCode 第104题。

然后你会发现 LeetCode 后面有些算法题需要用到这个算法的变形，比如第110题、543题。这两道题，如果你知道二叉树深度算法的递归过程，就很容易做出来。

关于二叉树的相关知识，可以看我的这篇文章： 数据结构】树的简单分析总结（附js实现）

题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。
复制代码

注意这里的二叉树是通过 链式存储法 存储的，而不是数组。

1. 递归是什么

在解题之前，我们先了解下什么是递归（如果你已经掌握，请直接跳过这节）。

那么就开始朗（wang）诵（ba）课本（nian）内容（jing）。

递归分为 “递” 和 “归”。“递” 就是传进去，“归”就是一个函数执行完解决了一个子问题。我们不停地将问题进行分解，A 分成 B 和

递归的核心在于递归公式，当我们分析出递归公式后，递归问题其实也就解决了。递归是一种应用广泛的编程技巧，很多地方都要用到它，比如深度优先遍历（本题就用到这个）、二叉树的前中后序遍历。

递归需要满足三个条件：

1. 可以分解为多个子问题；
2. 子问题除了数据规模不同，求解思路不变；
3. 存在递归终止条件。

递归的特点是代码比较简洁，虽然大多数情况下你都比较难理解递归的每个过程，因为它不符合人类的思维习惯，但其实你也不必去真正了解，你只要知道B和 C 被解决后，可以推导出 A 就行，无需考虑 B 和 C 是如何通过子问题解决的（因为都和前面一样的！）。

其次递归如果太深，可能会导致内存用尽。因为递归的时候要保存许多调用记录，就会维护一个调用栈，当栈太大而超过了可用内存空间，就会发生内存溢出的情况，我们称之为 堆栈溢出 。解决方案有下面 4 种：

1. 递归调用超过一定深度之后，直接报错，不再递归下去。 深度到底到多少会发生溢出，并不能通过计算得出，另外报错也导致程序无法继续运行下去，所以这个方案虽然确实可以防止内存溢出，并好像没有什么用。
2. 缓存重复计算。 递归可能会重复调用已经求解过的 f(k) 的结果，对于这种情况，就要对 f(k) 进行缓存，一般用哈希表来缓存（js 中可以通过对象实现）。当我们第二次执行 f(k) 时，直接从缓存中获取即可。
3. 改为非递归代码。 其实就是改为循环的写法。修改后的循环写法本质上也是递归，只是我们手动地实现了递归栈而已。循环写法代码实现会比递归复杂，而且也不够优雅。
4. 尾递归。 使用的是一种 尾调用优化 的技术，需要看运行环境是否提供这种优化。在支持尾调用优化的情况下，如果函数 A 的 最后一步 调用另一个函数 B，那进入 B 时，就不会保留 A 的调用记录（比如一些 A 的内部变量），这样就不会产生很长的调用栈，而导致堆栈溢出了。

说到递归，那就不得不提递归的一道经典题目了，那就是“爬楼梯问题”，对应LeetCode 第70题。

爬楼梯的问题描述是：假设你正在爬楼梯。需要 n （正整数）阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

首先你可以列出 n = 1，n = 2... 的走法，试着找出规律。

到这里我们就可以发现一些规律了。那就是 走到第 3 阶的走法为 2 阶 和 1 阶的和。为什么会这样呢？我们就要透过现象发现本质，本质就是，要走到第 n 阶，首先就要先走到 第 n-1 阶，然后再爬一个台阶，或者是先走到 n - 2 阶，然后爬两个台阶。

所以我们得到这么一个递归公式： f(n) = f(n-1) + f(n - 2)

递归写法：

var climbStairs = function(n) {
    let map = {};
    function f(n) {
        if (n < 3)  return n;
        if (map[n]) return map[n];
        
        let r =  f(n-1) + f(n - 2);
        map[n] = r;
        return r;
    }
    return f(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 = Math.log2(n+1) ，其中 k 为深度，n 为满二叉树的节点个数。那么对于一个完全二叉树来说，将 k 向上取整即可： k = Math.ceil( Math.log2(n+1) ) 。

所以对于一个顺序存储法存储的长度为 n 的二叉树，其高度 k 为：

k = Math.ceil( Math.log2(n+1) )
复制代码

（需要注意的是，这里的数组是从 0 开始存储节点的。）