LeetCode 题解工作台
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科 中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（ 一个节点也可以是它自己的祖先 ）。” 示例 1： 输入： root = [3,5,1…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们递归遍历二叉树： 如果当前节点为空或者等于 或者 ，则返回当前节点；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点5和节点1的最近公共祖先是节点3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
解题思路
方法一：递归
我们递归遍历二叉树：
如果当前节点为空或者等于 或者 ，则返回当前节点；
否则，我们递归遍历左右子树，将返回的结果分别记为 和 。如果 和 都不为空，则说明 和 分别在左右子树中，因此当前节点即为最近公共祖先；如果 和 中只有一个不为空，返回不为空的那个。
时间复杂度 ，空间复杂度 。其中 为二叉树节点个数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(
self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
if root in (None, p, q):
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
return root if left and right else (left or right)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) in all approaches, where n is the number of nodes, because each node is visited once. Space complexity is O(h) for recursion stack or O(n) for parent mapping, with h being the tree height. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check whether your solution handles one node being the ancestor of the other.
- question_mark
Ensure you efficiently track state without redundant traversals to meet O(n) time.
- question_mark
Consider whether recursive backtracking or parent mapping aligns better with memory constraints.
常见陷阱
外企场景- error
Failing to account for a node being a descendant of itself can return incorrect LCA.
- error
Overlooking null child nodes when propagating results may cause wrong merges in DFS.
- error
Confusing iterative parent tracking with naive BFS can increase space usage unnecessarily.
进阶变体
外企场景- arrow_right_alt
Finding LCA in a Binary Search Tree allows value comparisons to prune subtrees.
- arrow_right_alt
Determine LCA when nodes may not exist, requiring additional existence checks.
- arrow_right_alt
Find LCA for multiple pairs of nodes efficiently using a single traversal with preprocessing.