對于一個(gè)沒有重復(fù)元素的整數(shù)數(shù)組，請用其中元素構(gòu)造一棵MaxTree泉手，MaxTree定義為一棵二叉樹黔寇，其中的節(jié)點(diǎn)與數(shù)組元素一一對應(yīng)，同時(shí)對于MaxTree的每棵子樹斩萌，它的根的元素值為子樹的最大值》炜悖現(xiàn)有一建樹方法，對于數(shù)組中的每個(gè)元素颊郎，其在樹中的父親為數(shù)組中它左邊比它大的第一個(gè)數(shù)和右邊比它大的第一個(gè)數(shù)中更小的一個(gè)倘是。若兩邊都不存在比它大的數(shù)，那么它就是樹根袭艺。請?jiān)O(shè)計(jì)O(n)的算法實(shí)現(xiàn)這個(gè)方法。
方法不容易想到叨粘，直接說結(jié)論：
-
對于每個(gè)元素猾编，找到其左邊第一個(gè)大于它的數(shù)，和右邊第一個(gè)大于它的數(shù)：
-
對于某個(gè)元素來說升敲，如果左右數(shù)存在答倡，則較小者即為它的父節(jié)點(diǎn)；若左右其一不存在驴党，存在者即為父節(jié)點(diǎn)瘪撇；否則沒有父節(jié)點(diǎn)。
驗(yàn)證正確性：
- 除了最大數(shù)以外，每個(gè)數(shù)都可找到一個(gè)父親倔既。所以一定會構(gòu)成樹恕曲。
-
任何數(shù)在單獨(dú)一側(cè)的孩子至多有一個(gè)。假設(shè)K1K2都是A的孩子渤涌，則A>K1且A>K2.假設(shè)K1<K2則K1必以K2做父節(jié)點(diǎn)佩谣，而非A。同理可證实蓬。
關(guān)鍵步驟在于：
求序列中某個(gè)元素左邊和右邊第一個(gè)大于它的數(shù)茸俭。
類似于之前的算法，需要借助棧：
遍歷到元素x時(shí)安皱，
情況1：s為空或x<s.top() :記錄x的左端第一個(gè)比它大的值是空或s.top();壓入x;
情況2：彈出s的頂部元素直至滿足情況1為止调鬓。
從左向右遍歷和再從右向左遍歷，分別算出某元素左邊和右邊第一個(gè)大于它的數(shù)酌伊。
然后綜合這兩張表腾窝，得到每個(gè)元素的父節(jié)點(diǎn)編號。
如果需要組建二叉樹腺晾，建議生成一個(gè)哈希表燕锥，表的內(nèi)容為數(shù)組中某個(gè)元素，對應(yīng)二叉樹結(jié)點(diǎn)的地址悯蝉。數(shù)組每個(gè)元素先new產(chǎn)生結(jié)點(diǎn)归形，結(jié)點(diǎn)地址裝入哈希表。然后遍歷父節(jié)點(diǎn)編號列表鼻由，在父與子之間做指針域的鏈接暇榴。
這樣的話，在生成父節(jié)點(diǎn)編號表的時(shí)候蕉世，就可以留意看看哪個(gè)元素是根節(jié)點(diǎn)蔼紧，預(yù)先保存下來。當(dāng)然這里就不做實(shí)現(xiàn)了狠轻。
CODE
void firstBigL(const vector<int>&A,vector<int>& firstBiger){
int n=A.size();
firstBiger.resize(n);
stack<int>s;//注意里面存的是下標(biāo)
for(int i=0;i<n;++i){
while(!s.empty()&& A[s.top()]<A[i]){
s.pop();
}
if(s.empty())
firstBiger[i]=-1;
else
firstBiger[i]=s.top();
s.push(i);
}
}
void firstBigR(const vector<int>&A,vector<int>& firstBiger){
int n=A.size();
firstBiger.resize(n);
stack<int>s;//注意里面存的是下標(biāo)
for(int i=n-1;i>=0;--i){
while(!s.empty()&& A[s.top()]<A[i]){
s.pop();
}
if(s.empty())
firstBiger[i]=-1;
else
firstBiger[i]=s.top();
s.push(i);
}
}
vector<int> buildMaxTree(vector<int> A, int n) {
// write code here
vector<int> bigL,bigR;
firstBigL(A,bigL);
firstBigR(A,bigR);
for(int i=0;i<n;++i){
if(bigL[i]==-1)
bigL[i]=bigR[i];
else{
if(bigR[i]>-1 && A[bigR[i]]<A[bigL[i]])
bigL[i]=bigR[i];
}
}
return bigL;
}
如果元素有相等的情況
因?yàn)楹瘮?shù)中奸例，棧頂比x小就會彈出，如果相等就壓入x進(jìn)去向楼，所以最后的結(jié)果查吊，是數(shù)組左邊（右邊）第一個(gè)大于等于x的數(shù)。這樣的話湖蜕，照理也可以構(gòu)建大根堆逻卖，但是：
2 5 5 2
兩個(gè)5分別以對方作為父節(jié)點(diǎn)，建立失敗昭抒。
