LeetCode 补充题 207. 二叉树的最近公共祖先
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 236. 二叉树的最近公共祖先
力扣传入并返回节点对象，且两个目标不同；本文以节点值作为输入和输出，并允许两个目标相同。
:::
给定节点值互不相同的二叉树
root和两个目标值p、q，返回二者最近公共祖先的节点值。
示例 1：
输入：
root = [3,5,1], p = 5, q = 1
输出：3
提示：
- 树非空。
- 两个目标值都存在，允许二者相等。
题意分析
这是一棵普通二叉树，不能按节点值大小选择搜索方向。利用左右子树的递归返回值判断两个目标是否已经汇合；目标本身也可以成为公共祖先，且两个目标允许相同。
解法：后序递归汇合
核心思路
[!blue]
递归函数返回“当前子树里找到的目标节点或共同祖先”。空节点返回空；当前节点值命中 p 或 q 时返回自身，因为目标节点也可能是另一个目标的祖先。
左右递归都返回非空，说明两个目标分处两侧，当前节点就是汇合点；只有一侧非空时，将该侧结果继续上传。最外层只把最终节点转换成节点值。
按值比较依赖“节点值唯一且目标存在”的约定。面试先说明这个前提，才能把按节点身份判断的版本直接改为按值判断。
解题步骤
- 当前节点为空或命中任一目标值时，直接返回当前节点。
- 递归查询左右子树，得到各自找到的目标或公共祖先。
- 两侧都非空则返回当前节点，只有一侧非空则返回那一侧，都为空则返回空。
- 最外层读取返回节点的值，作为题目要求的答案。
代码实现
class Solution {
public int lowestCommonAncestor(TreeNode root, int p, int q) {
return findAncestor(root, p, q).val;
}
private TreeNode findAncestor(TreeNode root, int p, int q) {
if (root == null || root.val == p || root.val == q) {
return root;
}
TreeNode left = findAncestor(root.left, p, q);
TreeNode right = findAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}
func findAncestor(root *TreeNode, p int, q int) *TreeNode {
if root == nil || root.Val == p || root.Val == q {
return root
}
left := findAncestor(root.Left, p, q)
right := findAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
}
if left != nil {
return left
}
return right
}
func lowestCommonAncestor(root *TreeNode, p int, q int) int {
return findAncestor(root, p, q).Val
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：递归栈空间 $O(h)$。
关键点总结
[!green]
节点值唯一时，可用值比较定位目标；后序递归向上传递命中节点，左右两侧都有命中时当前节点即最近公共祖先。
易错点总结
[!yellow]
- 命中目标时直接返回，覆盖一个目标是另一个目标祖先的情况。
- p=q 时返回该目标自身，不需要在左右两侧各找到一次。
- 按值匹配依赖节点值唯一；最外层直接读取结果依赖两个目标都存在。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 236. 二叉树的最近公共祖先 | 中等 | 左右子树分别查找目标的递归过程相同；该题接收两个不同节点，本题以唯一节点值指定目标，并允许两个查询值相同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！