LCA问题 详细
1、二叉搜索树上找两个节点LCA
public int query(Node t, Node u, Node v) {
int left = u.value;
int right = v.value;
//二叉查找树内，如果左结点大于右结点，不对，交换
if (left > right) {
int temp = left;
left = right;
right = temp;
}
while (true) {
//如果t小于u、v，往t的右子树中查找
if (t.value < left) {
t = t.right;
//如果t大于u、v，往t的左子树中查找
} else if (t.value > right) {
t = t.left;
} else {
return t.value;
}
}
}
2、二叉树上找两个节点
node* getLCA(node* root, node* node1, node* node2)
{
if(root == null)
return null;
if(root== node1 || root==node2)
return root; node* left = getLCA(root->left, node1, node2);
node* right = getLCA(root->right, node1, node2); if(left != null && right != null) // 两个点在root的左右两边，就是root了
return root;
else if(left != null) // 哪边不空返回哪边
return left;
else if (right != null)
return right;
else
return null;
}
朴素法求解： 先对树进行dfs标出每一个节点的深度，对于查找的两个点先判断在不在同一深度，不在 移到统一深度，然后在往上找
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int Max = ;
int t, n, first, second, root;
vector<int> G[Max];
int indegree[Max], depth[Max], father[Max];
void inputTree()
{
for (int i = ; i <= n; i++)
{
G[i].clear();
father[i] = ;
indegree[i] = ;
depth[i] = ;
}
int u, v;
for (int i = ; i < n; i++)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
indegree[v]++;
father[v] = u;
}
scanf("%d%d", &first, &second);
for (int i = ; i <= n; i++)
{
if (indegree[i] == )
{
root = i;
break;
}
}
}
void dfs_depth(int u, int dep)
{
depth[u] = dep;
int Size = G[u].size();
for (int i = ; i < Size; i++)
{
dfs_depth(G[u][i], dep + );
}
}
int find_ancestor()
{
while (depth[first] > depth[second])
{
first = father[first];
}
while (depth[first] < depth[second])
{
second = father[second];
}
while (first != second) // 这样直接返回first
{
first = father[first];
second = father[second];
}
return first;
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
inputTree();
dfs_depth(root, );
printf("%d\n", find_ancestor());
}
return ;
}
tarjan + 并查集 解法：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int Max = ;
int t, n, first, second, root;
vector<int> G[Max], querry[Max];
int indegree[Max], father[Max], vis[Max];
void inputTree()
{
for (int i = ; i <= n; i++)
{
G[i].clear();
querry[i].clear();
father[i] = i;
indegree[i] = ;
vis[i] = ;
}
int u, v;
for (int i = ; i < n; i++)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
indegree[v]++;
}
scanf("%d%d", &first, &second);
querry[first].push_back(second);
querry[second].push_back(first);
for (int i = ; i <= n; i++)
{
if (indegree[i] == )
{
root = i;
break;
}
}
}
int find_father(int x)
{
if (x == father[x])
return x;
return father[x] = find_father(father[x]);
}
void unionSet(int x, int y)
{
x = find_father(x);
y = find_father(y);
if (x != y)
father[y] = x;
}
void tarjan(int x)
{
int Size = G[x].size();
for (int i = ; i < Size; i++)
{
int v = G[x][i];
tarjan(v);
unionSet(x, v);
}
vis[x] = ;
/*
if (x == first && vis[second])
printf("%d\n", find_father(second));
else if (x == second && vis[first])
printf("%d\n", find_father(first));
*/
Size = querry[x].size();
for (int i = ; i < Size; i++)
{
if (vis[querry[x][i]])
{
printf("%d\n", find_father(querry[x][i]));
return;
}
} }
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
inputTree();
tarjan(root);
}
return ;
}