复盘 · LC 236 二叉树的最近公共祖先

题目

题号：LeetCode 236
名称：二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree）
难度：Medium
链接：leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
今日代码：236-二叉树的最近公共祖先/index.js

题意

给定二叉树根节点 root，以及树中两个节点 p、q，返回它们的最近公共祖先（LCA）。

LCA：p、q 的共同祖先里，离它们最近的那个；节点可以是自己的祖先。
题目保证 p、q 都在树中；用节点引用比较，不是比 val。
边界：p/q 互为祖孙；p/q 就是根；左右子树各一个。

涉及算法

标签	一句话
后序递归	左右子树「是否找到 p/q」；两边都有 → 当前是 LCA
路径记录	先记下根到 p、根到 q 的路径，再找最后相同节点

教程对照：16 · 二叉树遍历、17 · 二叉树递归经典。

评价我的解法

你的思路：DFS 回溯记下根到 p / q 的整条路径，再并行走路径找最后一个相同节点。语义正确，能 AC，但提交很慢（约 130ms 仅 8%、内存约 90MB）。

我的代码（摘自 236-二叉树的最近公共祖先/index.js，不含本地测例）：

javascript

var lowestCommonAncestor = function (root, p, q) {
  const pPath = [];
  const qPath = [];
  function path(root, arr) {
    if (!root) {
      return;
    }
    arr.push(root);
    if (root === p) {
      pPath.push(...arr);
    }
    if (root === q) {
      qPath.push(...arr);
    }
    path(root.left, arr);
    path(root.right, arr);
    arr.pop();
  }

  path(root, []);
  let sameNode = root;
  let pNode = pPath[0],
    qNode = qPath[0];
  let i = 0;
  while (pNode && qNode) {
    if (pNode === qNode) {
      sameNode = pNode;
    }
    i++;
    pNode = pPath[i];
    qNode = qPath[i];
  }
  return sameNode;
};

对在哪、糙在哪：

路径 + 公共前缀是对的：用节点引用 === 比较也对。
找到 p/q 后仍整棵树扫完：没有剪枝；大树浪费明显。
pPath.push(...arr) 拷贝整条路径：额外 O(h) 复制，且两份路径常驻内存，解释了高内存占用。
未找到时仍依赖 sameNode = root：题目保证有解还行；若一边路径为空，逻辑会脆。
复杂度：一次 DFS 仍是 O(n)，但常数与空间都比标准后序解差一截——提交排名偏低主要来自这里，不是算法量级错了。

小结：能讲清「祖先路径的最长公共前缀」；面试更该默写后序递归一趟返回 LCA，少存路径。

最佳题解

后序递归（标准面试写法）：

javascript

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
};

时间 O(n)，空间 O(h) 递归栈。
为何更优：
- 空 / 命中 p 或 q → 直接返回（「在这棵子树里找到了谁」）。
- 左右都非空 → 当前节点就是 LCA。
- 只有一边非空 → LCA 在那一边（含「p 是 q 祖先」的情况）。
- 不显式存路径，常数小、好口述。

关联题目

题	为何相关
235. 二叉搜索树的最近公共祖先	同一问题；BST 可按值走左/右，不必后序两边搜
1644. 二叉树的最近公共祖先 II	p/q 可能不在树中，要改返回语义
112. 路径总和	根到某节点路径思想；你今天存路径的变体
865. 具有所有最深节点的最小子树	「汇合点」递归套路同类

一句话带走

普通二叉树 LCA：后序看左右；两边都找到就返回当前，否则返回非空那侧——别先存两条路径再比对。

复盘 · LC 236 二叉树的最近公共祖先 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​