題意：

給出一棵二叉搜索樹(shù)的前序遍歷，問(wèn)結(jié)點(diǎn)u和v的共同最低祖先是誰(shuí)，利用先序遍歷特點(diǎn)。
二叉搜索樹(shù)滿足：
節(jié)點(diǎn)的左子樹(shù)只包含鍵小于節(jié)點(diǎn)鍵的節(jié)點(diǎn)。
節(jié)點(diǎn)的鍵只包含節(jié)點(diǎn)的右鍵大于或等于子樹(shù)的節(jié)點(diǎn)的鍵。
左子樹(shù)和右子樹(shù)也必須是二叉搜索樹(shù)。

題解：

樣例：
6 3 1 2 5 4 8 7
根據(jù)題目要求我們可以得到：

紅字則是該數(shù)字在前序遍歷中出現(xiàn)的順序（從0開(kāi)始）
我們可以從題目要求下手，在本題中，根的左子樹(shù)總是小于根，右子樹(shù)總是大于根
查詢u和v的lca，如果一個(gè)x（x不與u和v重合）同時(shí)滿足x>u,x<v,說(shuō)明u在x的左邊，v在x的右邊，那說(shuō)明x就是u和v的lca
同理。x<u,x>v也是
當(dāng)然x和u或v重合時(shí)也是

代碼：

#include<bits/stdc++.h> using namespace std; map<int,bool> mp; int main(){int m,n,u,v,a;cin>>m>>n;vector<int> pre(n);for (int i=0;i<n;i++){cin>>pre[i];mp[pre[i]]=true;}for (int i=0;i<m;i++){cin>>u>>v;for (int j=0;j<n;j++){a=pre[j];if ((a>u&&a<v)||(a>v&&a<u)||(a==u)||(a==v))break;}if (mp[u]==false&&mp[v]==false)printf("ERROR: %d and %d are not found.\n",u,v);else if (mp[u] == false || mp[v] == false)printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);else if (a == u || a == v)printf("%d is an ancestor of %d.\n", a, a == u ? v : u);elseprintf("LCA of %d and %d is %d.\n", u, v, a);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的1143 Lowest Common Ancestor 甲级的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。