二叉树的最近公共祖先
Lowest Common Ancestor of a Binary Tree
本机进度仅保存在当前浏览器
题目描述
给定一个二叉树，找到该树中两个指定节点 p 和 q 的最近公共祖先（LCA）。祖先的定义为：如果节点 p 在节点 root 的子树中，或 p == root，那么 root 是 p 的祖先。
示例：树 [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]，p = 5，q = 1，LCA 为 3。
解题思路
- 后序递归：对每个节点，先在左右子树中分别查找 p、q。
- 若左右子树各命中一个，当前节点即最近公共祖先（p、q 分居两侧，交汇点必是 LCA）。
- 若只有一侧命中，说明两个目标都在那一侧（或一个目标本身就是祖先），把命中结果向上传递。
- 递归基：节点为空返回 None，等于 p 或 q 返回自身。
参考实现
查看参考实现Python · 建议先自行作答
def lowestCommonAncestor(root, p, q):
# 后序遍历：自底向上汇聚命中信息
if not root or root is p or root is q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else right