题目描述：
给出一棵二叉树，找出指定两个节点的最近公共祖先（LCA）。
数据范围：
$2\le n \le 10^5$
题解：
由于只查询一组，所以没什么优化的必要。直接暴力就行。
如果查询多组，就需要使用倍增法，RMQ法或者Tarjan了。其中tarjan是离线算法，其他两个是在线算法，一般使用倍增比较好写，比较简单。
代码：
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
| class Solution {
public:
unordered_map<TreeNode*, TreeNode*> mp;
unordered_set<TreeNode*> st;
void dfs(TreeNode* root, TreeNode* fa)
{
if(root == nullptr) return;
mp[root] = fa;
dfs(root->left, root);
dfs(root->right, root);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root, nullptr);
while(p)
{
st.insert(p);
p = mp[p];
}
while(q)
{
if(st.count(q)) return q;
q = mp[q];
}
return nullptr;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
if (root == nullptr || root == p || root == q)
return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if (left == nullptr && right == nullptr)
return nullptr;
if (left && right)
return root;
if (left)
return left;
if (right)
return right;
return nullptr;
}
};
|
倍增法：
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
unordered_map<TreeNode *, unordered_map<int, TreeNode *>> fa;
unordered_map<TreeNode *, int> depth;
void dfs(TreeNode *root, TreeNode *p, int dep)
{
if (root == nullptr)
return;
fa[root][0] = p;
depth[root] = dep;
dfs(root->left, root, dep + 1);
dfs(root->right, root, dep + 1);
}
void build()
{
for (int k = 1; k < 17; ++k)
{
for (auto &root : depth)
{
fa[root.first][k] = fa[fa[root.first][k - 1]][k - 1];
}
}
}
TreeNode *query(TreeNode *p, TreeNode *q)
{
if (depth[p] < depth[q])
swap(p, q);
int tmp = depth[p] - depth[q];
for (int i = 17; i >= 0; --i)
{
if (tmp >= (1 << i))
{
p = fa[p][i];
tmp -= (1 << i);
}
}
if (p == q)
return p;
for (int i = 17; i >= 0; --i)
{
if (depth[p] >= (1 << i))
{
if (fa[p][i] != fa[q][i])
{
p = fa[p][i];
q = fa[q][i];
}
}
}
return fa[p][0];
}
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
dfs(root, nullptr, 0);
build();
return query(p, q);
}
};
|