描述

前面我们学习过了树这种特殊的数据结构。我们知道除了根结点，树上的每个都有父结点。这里我们提到另外一个概念，祖先 结点。所谓祖先结点，就是父结点的父结点，父结点的父结点的父结点…，所有沿着父亲结点向根结点走的结点都能称为祖先结点。特殊的是，自己也可以称为自己的祖先结点。

两个结点的最近公共祖先结点就是这两个结点沿着父节结点一直到根结点的路径上第一个相遇的结点。给出一棵树，求出树上的两个结点的最近公共祖先。

输入
输入第一行一个整数 n(1 ≤ n ≤ 1000) 表示树的结点数，结点的编号为 1 到 n。

接下来一行，输入 n 个用空格隔开的整数，第 i 个整数表示结点 i 的父亲节点。如果是 -1 表示该结点为根节点。

接下来一行输入两个整数 u, v(1 ≤ u, v ≤ n)。

输出
输出结点 u 和 v 的最近公共祖先结点的编号。

输入样例 1

5
-1 1 2 2 1
5 4
输出样例 1

1
输入样例 2

7
4 6 1 7 2 7 -1
6 5
输出样例 2

6

这道题目其实很简单，对于第一个点，可以一直递归的访问父亲结点直到根结点，用一个set来记录第一个点到根节点路径上的点。然后对于第二个点，也递归的访问父亲结点，遇到的第一个在set中出现过的点就是他们的公共祖先。
代码实现其实用两个数组就可以完成，因为这道题数据范围较小，最后校验的时候跑O(n^2)也不会炸的。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1010];
int a11[1010],a22[1010];
int main()
{
    int ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a[i]=x; 
    }
    int a1,a2;
    cin>>a1>>a2;
    int sum;
    sum=a1;
    while(sum!=-1)
    {
        ans++;
        a11[ans]=sum;
        sum=a[sum];
    }
    sum=a[a2];
    int aaa=ans;
    ans=0;
    while(sum!=-1)
    {
        ans++;
        a22[ans]=sum;
        sum=a[sum];
    }
    for(int i=1;i<=aaa;i++)
    {
        for(int j=1;j<=ans;j++)
        {
            if(a11[i]==a22[j])
            {
                cout<<a11[i];
                return 0;
            }
        }
    }
    return 0;
}

ov

个人博客地址: www.moyujiang.com 或 moyujiang.top