考察点:LCA 递归剪枝写法、边界条件、复杂度。这是二叉树追问链里「综合递归 + 分治」的高阶题。
要点:
p 或 q 等于 root(自身即祖先),或其一在左、另一在右,则 root 就是 LCA;否则 LCA 在 p、q 所在的那一侧子树里。参考实现(剪枝写法,每节点只走一次):
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 是否各自在左右子树、再递归」——那样会重复遍历;上面的写法靠返回值向上汇合,天然只走一次。
题目与答案就在本页;收藏、批注和错题重练在应用内