輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷結(jié)果。如果是則返回?true，否則返回?false。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。

?

參考以下這顆二叉搜索樹：

? ? ?5
? ? / \
? ?2 ? 6
? / \
?1 ? 3
示例 1：

輸入: [1,6,3,2,5]
輸出: false
示例 2：

輸入: [1,3,2,6,5]
輸出: true
?

提示：

數(shù)組長度 <= 1000

代碼：

class?Solution?{

????public?boolean?verifyPostorder(int[]?postorder)?{

????????if(postorder.length==0)

????????{

????????????return?true;

????????}

????????return?find(postorder,0,postorder.length-1);

????}

????public?boolean?find(int[]?postorder,int?start,int?end)

????{

????????if(start>=end)

????????{

????????????return?true;

????????}

????????int?i?=?start,j?=?end-1;

????????while(i<end&&postorder[i]<postorder[end])

????????{

????????????i++;

????????}

????????while(j>start&&postorder[j]>postorder[end])

????????{

????????????j--;

????????}

????????if(i<j)

????????{

????????????return?false;

????????}

????????return?find(postorder,start,i-1)&&find(postorder,j+1,end-1);

????}

}

總結(jié)

以上是生活随笔為你收集整理的【剑指offer】面试题33：二叉搜索树的后序遍历序列（Java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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