描述

前面我們學習過了樹這種特殊的數據結構。我們知道除了根結點，樹上的每個都有父結點。這里我們提到另外一個概念，祖先 結點。所謂祖先結點，就是父結點的父結點，父結點的父結點的父結點…，所有沿著父親結點向根結點走的結點都能稱為祖先結點。特殊的是，自己也可以稱為自己的祖先結點。

兩個結點的最近公共祖先結點就是這兩個結點沿著父節結點一直到根結點的路徑上第一個相遇的結點。給出一棵樹，求出樹上的兩個結點的最近公共祖先。

輸入
輸入第一行一個整數 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

總結

以上是生活随笔為你收集整理的【题解】最近公共祖先的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。