分析
-
使用递归深度优先搜索（DFS）
- 状态定义：
- 如果某个子树中找到了
p ，则返回状态 1
- 如果找到了
q ，则返回状态 2
- 如果同时找到
p 和 q，状态为 3
- 递归逻辑：
- 对当前节点的左右子树分别进行递归
- 将左右子树的状态结果与当前节点的状态进行合并（按位或操作）
- 如果当前节点的状态等于
3 且最近公共祖先 res 尚未被赋值，则更新 res
-
终止条件
- 当
p 和 q 在同一个子树中时，递归会找到它们最近的公共祖先并停止
- 如果两个节点在不同子树中，递归逻辑会找到分叉点，即最近公共祖先
时间复杂度
时间复杂度 O(n)，其中 n 是二叉树的节点总数，每个节点访问一次
空间复杂度
空间复杂度为 O(h)，其中 h 是二叉树的高度，递归调用栈的深度
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution
{
public:
TreeNode* res = nullptr; // 存储最近公共祖先节点
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
dfs(root, p, q); // 执行深度优先搜索
return res; // 返回最近公共祖先
}
int dfs(TreeNode* root, TreeNode* p, TreeNode* q)
{
int state = 0; // 当前节点的状态
if (!root)
return state; // 如果当前节点为空，返回状态 0
if (root == p)
state |= 1; // 如果找到节点 p，更新状态为 1
else if (root == q)
state |= 2; // 如果找到节点 q，更新状态为 2
// 递归左右子树
state |= dfs(root->left, p, q);
state |= dfs(root->right, p, q);
// 如果当前状态为 3（即同时找到 p 和 q），且 res 尚未更新，更新 res
if (state == 3 && !res)
res = root;
return state; // 返回当前节点的状态
}
};
|
