Sunday面试指南

二叉树的直径怎么求?为什么最长路径不一定经过根节点?

以下对话为教学模拟,用来讲解这道题。

🧑‍💻 面试官:二叉树直径是不是左子树高度加右子树高度?

🙋‍♂️ 我:是,把根左右两边最长的路径接起来就行。

🧑‍💻 面试官:如果最长路径完全位于左子树里面呢?

🙋‍♂️ 我:那每个节点都需要检查,不能只检查根。

🧑‍💻 面试官:检查完一棵子树,交给父节点的是这棵子树的直径,还是一条向下的高度?两条分叉都能往上接吗?

向父节点返回的是一条能继续延长的路径;直径则可以在当前节点把两条向下路径接起来。

面试速答(60 秒版)

二叉树直径是任意两个节点之间最长路径的边数,不要求经过整棵树的根,也不是节点数。

可以后序遍历。先得到左右子树高度,再用左右高度之和更新全局直径;交给父节点的高度,则只能取左右较大者加一,因为继续向上延伸的路径不能同时带着两条分支。

这里约定空树高度为 0,叶子高度为 1,那么左右高度之和正好是穿过当前节点的路径边数。所有节点都检查一次,才能覆盖最长路径藏在某个子树里的情况。

时间 O(n)。递归写法需要 O(h) 调用栈,但深链有栈溢出风险;下面用显式后序栈和高度表避免递归,额外空间相应为 O(n)。

每节点向父给一条路径全局候选可拼两条

知识点详解:高度是向上交的数据,直径是沿途更新的答案

先把长度单位固定下来

只有一个节点,直径为 0,因为没有边。两个相连节点,直径为 1。

本题把 height 定义为向下路径包含的节点数,空节点为 0,叶子为 1。某节点左侧高度是 2,右侧高度是 3,穿过它的最长路径就有 2+3 条边。

为什么不用再减一?左侧高度虽然按节点数记,但从当前节点连到左子树最深处,正好需要同样多的边。左右两侧加起来,当前节点没有被重复按节点计数。

高度也可以定义为边数,但空树初值与公式都要一起修改。面试最容易出错的是前半段按一种单位,代码后半段又换了一种。

根可能只是最长路径旁边的一条短分支

假设根 R 只有左孩子 A,A 左右各有一条长度为 2 条边的向下分支,分别到 D 和 E。

最长路径可以从 D 经过 A 到 E,共 4 条边。经过 R 的路径反而只能沿某一侧走到 D 或 E,共 3 条边。

因此,不能只计算根节点的左右高度之和。应该在 A 处发现 4,在其他节点也检查候选,最后保留全局最大值。

R只连A而最长D-B-A-C-E不经过R

为什么返回值不能也用左右高度之和?

因为父节点需要的是一条可以接上来的路径。如果 A 已经把两边拼成 D 到 E,再连接父节点 R,路径就会在 A 处分成三条方向,不再是一条简单路径。

所以每个节点做两件不同的事:用左右高度的和尝试更新答案,再把 1 + max(左高度, 右高度) 交给父节点。

这也是后序的原因。左右孩子还没处理完,当前节点就不知道它们能提供多长的向下路径。

用显式栈完成后序计算

下面假定输入是真正的二叉树,没有环,也没有多个父节点共享同一个孩子。空树返回 0。expanded 表示孩子已经安排处理,第二次回到当前节点时才计算高度。

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };

function diameter(root: TreeNode | null): number {
  if (!root) return 0;
  const stack: [TreeNode, boolean][] = [[root, false]];
  const heights = new Map<TreeNode, number>();
  let best = 0;
  while (stack.length) {
    const [node, expanded] = stack.pop()!;
    if (!expanded) {
      stack.push([node, true]);
      if (node.right) stack.push([node.right, false]);
      if (node.left) stack.push([node.left, false]);
    } else {
      const left = node.left ? heights.get(node.left)! : 0;
      const right = node.right ? heights.get(node.right)! : 0;
      best = Math.max(best, left + right);
      heights.set(node, 1 + Math.max(left, right));
    }
  }
  return best;
}

Python 的 eq=False 保留节点的对象身份语义,节点才能作为字典键。不能把内容相同的两个节点合并成同一条高度记录。

每个节点入栈两次,处理次数仍然是常数。这里高度表最多保存 n 个节点,因此空间 O(n),不能因为没有递归,就宣称空间变成了 O(1)。题目路径与边数定义见 LeetCode 543。

显式后序栈expanded与高度表各司其职

面试官继续追问

节点值能不能用来当高度表的键?

不可以,树可能有重复值。高度属于具体节点,不属于某一个数值;使用节点身份,或者在输入层提供唯一节点 ID。

换成带权树,还能直接加高度吗?

需要重新定义向下路径状态,按边权计算,尤其要明确负权和是否允许空路径。当前代码只计算每条边长度为 1 的二叉树,不能直接套给任意带权图。

怎么测试不是只检查了根?

除了空树、单节点和长链,要专门构造最长路径在子树里的例子。小树可以从每个节点做无向遍历,枚举两点距离,与后序结果对照。深链则用于检查实现有没有偷偷依赖递归栈。

面试速记卡

  • 直径:任意两点最长路径的边数,不要求经过根。
  • 高度约定:空树 0、叶子 1,当前候选为左右高度之和。
  • 返回给父节点:只能带一条分支,取 max 后加一。
  • 全局答案:每个节点都检查,覆盖子树内的最长路径。
  • 本文迭代版:时间 O(n),高度表带来 O(n) 额外空间。

公司面试真题

真题根据求职者公开面经整理,题意经过概括,非逐字原话或公司官方题库;本文为 Sunday 的独立解析。

浏览公司面试真题 →
简历汪永久免费在线制作简历,模板直接套用、导出无水印,永久免费、下载免费,不需要付费解锁任何功能。去写简历