難度：中等
輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷結(jié)果。如果是則返回 true，否則返回 false逐工。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。
參考以下這顆二叉搜索樹：
5
/ \
2 6
/ \
1 3
示例 1：
輸入: [1,6,3,2,5]
輸出: false
解答思路：
后序遍歷的順序是 : 左子樹 | 右子樹 | 根節(jié)點漂辐。
二叉搜索樹的性質(zhì)：左子樹的值都小于根節(jié)點泪喊，右子樹的值都大于根節(jié)點。
采用遞歸分治的方式將數(shù)劃分為左右子樹髓涯，然后遞歸檢查每個子樹的正確性（是否滿足后序遍歷和二叉搜索樹的性質(zhì)袒啼。）
遞歸的流程：
1）劃分左右子樹：遍歷數(shù)組 postorder 區(qū)間 [i, j]，逐個元素與根節(jié)點 postorder[j] 比較纬纪，尋找大于根節(jié)點的值的下標(biāo) m蚓再，此時區(qū)間 [i, m-1] 為左子樹，[m, j-1] 為右子樹包各。
2）檢查左右子樹是否滿足二叉搜索樹的性質(zhì)（左子樹的元素小于根節(jié)點摘仅，右子樹的元素大于根節(jié)點），因為左子樹 [i, m -1] 在尋找大于根節(jié)點的值的下標(biāo) m 時已經(jīng)檢查過了问畅，所以只需檢查右子樹 [m, j-1] 的元素是否大于根節(jié)點娃属。
3）遞歸檢查左右子樹的正確性（滿足后序遍歷和二叉搜索樹的性質(zhì)）。
遞歸結(jié)束的條件：i >= j护姆，也就是子樹中的節(jié)點數(shù)量小于等于1時矾端，此時無需檢查，返回 true卵皂。
class Solution {
public boolean verifyPostorder(int[] postorder) {
return checkout(0, postorder.length-1, postorder);
}
private boolean checkout(int i, int j, int[] postorder){
if(i >= j)
return true;
int m = j; //如果全部元素都小于根節(jié)點秩铆，也就是沒有右子樹，[i, m-1]就是左子樹灯变，之前錯放在 j-1 位置上殴玛。
// 劃分左右子樹
for(int k = i; k < j; k ++){
if(postorder[k] > postorder[j]){
m = k;
break;
}
}
// 檢查右子樹的元素是否都大于根節(jié)點
for(int k = m; k < j; k ++)
if(postorder[k] <= postorder[j])
return false;
// 檢查左右子樹是否滿足后序遍歷的性質(zhì)和二叉搜索樹的性質(zhì)
return checkout(i, m-1, postorder) && checkout(m, j-1, postorder);
}
}
代碼優(yōu)化:
int m = j;
//劃分左右子樹
for(int k = i; k < j; k ++){
if(postorder[k] > postorder[j]){
m = k;
break;
}
}
可以改為
int m = 0;
while(postorder[m] < postorder[j])
m++;
