68.二叉树的最大深度

题目

给定一个二叉树 root ，返回其最大深度。

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

思路

递归

核心思想: 把大问题拆成子问题

递归的精髓是“相信子问题已经解决了”。

想求整棵树的最大深度，我们换个角度想: 一棵树的深度，等于它左右两棵子树中较深的那个，再加上根节点自己这一层(+1)。

用一句话概括:

树的最大深度 = max(左子树的最大深度，右子树的最大深度) + 1

这就是递归的递推关系。

你会发现，求左子树的深度和求整棵树的深度是同一个问题，只是规模变小了。

递归的两个要素:

递归终止条件: 什么时候不用再往下递归了？
当前节点为空(null)时，深度为0，这就是递归的底，也是防止无限递归的关键。
递归推进(递推关系): 怎么用子问题的答案组合出当前答案？ max(左子树深度，右子树深度) + 1

用示例走一遍

求3的深度 = max(求9的深度，求20的深度) + 1
- 求9的深度 = max(左null=0, 右null=0) + 1 = 1(9是叶子)
- 求20的深度 = max(求15的深度，求7的深度) + 1
  - 求15的深度 = max(0, 0) + 1 = 1
  - 求7的深度 = max(0, 0) + 1 = 1
  - 所以20的深度是 = max(1, 1) + 1 = 2
- 所以3的深度 = max(1, 2) + 1 = 3

递归会自动“钻到底再往上返回”，我们只需要写好那一行递推关系，剩下的交给递归自己完成。

/**
 * 二叉树节点定义
 */
class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun maxDepth(root: TreeNode?): Int {
        // 1. 递归终止条件：空节点深度为 0
        if (root == null) {
            return 0
        }

        // 2. 分别求左右子树的最大深度（相信递归会给出正确答案）
        val leftDepth = maxDepth(root.left)
        val rightDepth = maxDepth(root.right)

        // 3. 当前树的深度 = 较深的子树 + 根节点自己这一层
        return maxOf(leftDepth, rightDepth) + 1
    }
}

方法二：层序遍历

策略是：

先处理第 1 层（只有 root）。处理它的时候，把它的孩子（第 2 层）都记下来（放进队列）。
再处理第 2 层的所有节点。处理它们时，把它们的孩子（第 3 层）记下来。
……如此反复，每处理完一整层，深度就 +1。
直到某一层的节点都没有孩子了，队列变空，结束。

最关键的技巧——如何"按层"分开处理？

这是很多人卡住的地方。队列里的节点是混在一起的，我怎么知道哪些是同一层的？

技巧：在处理每一层之前，先记录下"当前队列里有几个节点"，这个数量就是当前层的节点数。

因为在开始处理某一层时，队列里装的恰好就是这一层的全部节点（上一层处理时把它们加进来的，还没加入下一层）。所以：

val levelSize = queue.size // 此刻队列里的数量 = 当前这一层的节点数然后我们只处理这么多个节点（用一个 for 循环循环 levelSize 次），处理这些节点时把它们的孩子加到队尾。等这个 for 循环跑完，当前层就处理干净了，队列里剩下的全是下一层的节点。

这就是为什么代码里要有这么一行 val levelSize = queue.size——它是"按层切分"的关键。

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}


class Solution {
    fun maxDepth(root: TreeNode?): Int {
        if (root == null) {
            return 0
        }

        val queue: java.util.Queue<TreeNode> = LinkedList()
        // 把根节点加入队列
        queue.offer(root)
        var depth = 0

        while (queue.isNotEmpty()) {
            // 关键：先记下当前这一层有多少个节点
            val levelSize = queue.size
            // 把这一层的节点全部处理完，同时把它们的孩子加入队列（下一层）
            for (i in 0 until levelSize) {
                val node = queue.poll()
                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
            // 处理完一整层，深度 +1
            depth++
        }

        return depth
    }
}

复杂度

时间复杂度: O(n)：n 是节点总数，每个节点恰好被访问一次。
空间复杂度: O(h)：h 是树的高度，来自递归调用栈的深度。最坏情况（树退化成一条链）h = n，空间 O(n)；平衡树时 h = log n，空间 O(log n)。

下一题

邮箱：charon.chui@gmail.com
Good Luck!