IT 面试题库

求二叉树中两个节点的最近公共祖先(LCA),用递归实现并说清边界条件(节点等于 root、节点分列左右子树、空树)。

高级编程题算法工程师Java后端工程师二叉树LCA最近公共祖先递归分治

题目

考察点:LCA 递归剪枝写法、边界条件、复杂度。这是二叉树追问链里「综合递归 + 分治」的高阶题。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 70 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:

参考实现(剪枝写法,每节点只走一次):

function lowestCommonAncestor(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;   // 分列左右子树 → 当前即 LCA
  return left || right;             // 都在某一侧,或都没找到
}

易错点:不要写成「先判断 p/q 是否各自在左右子树、再递归」——那样会重复遍历;上面的写法靠返回值向上汇合,天然只走一次。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题