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

r囧r小猫 2022-04-27 22:48 176阅读 0赞

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

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

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

### 题目描述 ###

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

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

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

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

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

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

### 1. 递归是什么 ###

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

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

递归分为 “递” 和 “归”。“递” 就是传进去，“归”就是一个函数执行完解决了一个子问题。递归的实现通过不停地将问题分解为子问题，并通过解决子问题，最终解决原问题。

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

递归需要满足三个条件：

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题][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 开始存储节点的。）

### 参考 ###

1.  [阮一峰的网络日志——尾调用优化][Link 1]
2.  [数据结构与算法之美：10 | 递归：如何用三行代码找到“最终推荐人”？][10 _]

[LeetCode _104]: https://link.juejin.im?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fmaximum-depth-of-binary-tree%2F
[js]: https://juejin.im/post/5ccbe50ee51d453a7f5ece3a
[LeetCode _70]: https://link.juejin.im?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fclimbing-stairs%2F
[Link 1]: https://link.juejin.im?target=http%3A%2F%2Fwww.ruanyifeng.com%2Fblog%2F2015%2F04%2Ftail-call.html
[10 _]: https://link.juejin.im?target=https%3A%2F%2Ftime.geekbang.org%2Fcolumn%2Farticle%2F41440