二叉搜索樹(shù)的后序遍歷序列
題目描述
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷結(jié)果。如果是則返回 true，否則返回 false逗宁。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同领斥。
image
示例：
輸入: [1,6,3,2,5]
輸出: false
輸入: [1,3,2,6,5]
輸出: true
提示：
數(shù)組長(zhǎng)度 <= 1000
題目分析
- 二叉搜索樹(shù)的特點(diǎn)：
1.1. 左子樹(shù)的所有節(jié)點(diǎn)永遠(yuǎn)小于等于父節(jié)點(diǎn)
1.2. 右子樹(shù)的所有節(jié)點(diǎn)永遠(yuǎn)大于等于右子樹(shù)
1.3. 左子樹(shù)和右子樹(shù)也是二叉搜索樹(shù) - 后續(xù)遍歷的特點(diǎn)：左子樹(shù)先遍歷嫉到、右子樹(shù)后遍歷、父節(jié)點(diǎn)最后遍歷
舉例子： [1,3,2,6,5]
- 根據(jù)特點(diǎn)2月洛，根節(jié)點(diǎn)顯然是5
- 根據(jù)特點(diǎn)1.2何恶，我們可以從根節(jié)點(diǎn)往前探索，比它大的都是右子樹(shù)的嚼黔，剩下的都是左子樹(shù)的细层，所以右子樹(shù)是[6]，左子樹(shù)是[1,3,2]
- 然后對(duì)于特點(diǎn)1.1還沒(méi)有得到驗(yàn)證唬涧，所有對(duì)于左子樹(shù)[1,3,2]疫赎，都必須確保每個(gè)元素都比5小，否則不符合二叉搜索樹(shù)的特點(diǎn)碎节，返回false
- 如果特點(diǎn)1.1得到驗(yàn)證捧搞，那么只要證明特點(diǎn)1.3，整棵樹(shù)就是滿(mǎn)足二叉搜索樹(shù)的特點(diǎn)了狮荔，1.3的證明很簡(jiǎn)單实牡，對(duì)左子樹(shù)和右子樹(shù)也進(jìn)行像整棵樹(shù)一樣的操作即可（遞歸）
public boolean verifyPostorder(int[] postorder) {
if(postorder.length == 1) return true;
return verifyPostorder(postorder,0,postorder.length-1);
}
//驗(yàn)證當(dāng)前數(shù)是否為二叉搜索樹(shù)
public boolean verifyPostorder(int[] postorder,int head,int tail) {
if(head >= tail) return true;
int parent = postorder[tail];
int rightHead = tail;
//尋找右子樹(shù)和左子樹(shù)的分界點(diǎn)
while(rightHead >= head){
if(postorder[rightHead] >= parent)
rightHead--;
else
break;
}
rightHead += 1;
// 驗(yàn)證右子樹(shù)是否為二叉搜索樹(shù)
if(!verifyPostorder(postorder,rightHead,tail-1))
return false;
// 驗(yàn)證左子樹(shù)是否都比父節(jié)點(diǎn)小
if(!verifyLeft(postorder,head,rightHead-1,parent))
return false;
// 驗(yàn)證左子樹(shù)是否為二叉搜索樹(shù)
return verifyPostorder(postorder,head,rightHead-1);
}
public boolean verifyLeft(int[] postorder,int head,int tail,int parent){
for(int i = head; i <= tail; i++){
if(postorder[i] > parent)
return false;
}
return true;
}
