LeetCode 二叉树的最大深度 DFS 题解

题目

二叉树的最大深度

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

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

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

解题思路

新建一个变量，记录最大深度
深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量
遍历结束返回最大深度这个变量

求最大深度必须走完所有分支，因为最深的那条路径可能在任何位置，不看完无法确定。这一点和求最小深度不同——最小深度可以在找到第一个叶子节点时提前结束，用广度优先能剪掉大量搜索。既然本题反正要遍历全部节点，用深度优先就够了，而且递归写起来更短。

「记录每个节点的层级」这件事，靠给递归函数多加一个参数来完成。这是递归里很常用的手法：把当前状态沿着调用链往下传，每深一层就把值加一。

只在叶子节点处更新答案，是因为深度的定义是「根到最远叶子的路径节点数」，中间节点的层级不可能是最终答案——它下面还有节点，路径还能更长。

这道题还有一种更简洁的递归写法，思路是换个角度：一棵树的最大深度，等于左右子树最大深度的较大值加一，也就是 return root ? Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 : 0。它不需要外部变量和层级参数，是自底向上把结果一层层汇总回来，属于后序思路；而下面这个实现是自顶向下传递层级，属于先序思路。两种都对，后者更容易改造成需要路径信息的题目。

题解

res 存最大深度，dfs 的第二个参数 l 是当前节点所在的层级。

var maxDepth = function (root) {
  let res = 0;
  const dfs = (n, l) => {
    if (!n) return;
    if (!n.left && !n.right) {
      res = Math.max(res, l);
    }

    dfs(n.left, l + 1);
    dfs(n.right, l + 1);
  };

  dfs(root, 1);

  return res;
};

几个点值得注意。

初始调用传的是 dfs(root, 1) 而不是 0，因为题目定义深度是路径上的节点数，根节点自己就算一层。传 0 的话结果会少一。

if (!n) return 这一行同时干了两件事：作为递归终止条件，以及处理空树。空树时根本进不到后面的逻辑，res 保持初始值 0 返回，符合题目预期。

res 定义在 dfs 外面，靠闭包被内层函数访问和修改。这是递归中收集结果的常见写法，比通过返回值层层传递更直观，代价是函数不再是纯函数。

判断叶子节点用的是 !n.left && !n.right，两个孩子都为空才算叶子。只判断一个是不够的——单侧有孩子的节点不是叶子，但路径还能往下延伸。

时间复杂度：O(n)

每个节点访问一次。空间复杂度是 O(h)，h 为树高，来自递归调用栈。最坏情况树退化成链表，h 等于 n，空间是 O(n)，节点数极多时有栈溢出的风险；平衡树的话是 O(log n)。这也是深度优先递归解法唯一需要留意的地方。