題目描述

輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。

解題思路

比如下面的這棵二叉搜索樹

它的后序遍歷為0214369875；
我們設當前根節點為root;
第一次root=5
我們可以看出以3和6中間為分割線，左邊為5的左子樹，右邊為5的右子樹，數組最后一個數為5，為根結點。所以 {0,2,1,4,3}<root;{6,9,8,7}>root
size–1;
root = 7;
去掉5，最后一個數為7，它是以5為根結點的右子樹，那么它肯定大于以5為根節點的左子樹并且大于本身的左子樹
{0,2,1,4,3}<root;{6}<root;{9,8}>root;
size–1;
root = 8;
當數據規模再減1時，則走到了根結點的右子樹的右子樹，那么此時的root，它肯定大于以5為根節點的左子樹，和以7為根節點的左子樹，和自身的左子樹，小于自身的右子樹
那么size–1一直持續下去，數組最后一個根節點永遠都是上述的結論，就算到以5為根結點的左子樹中也成立，所以再這個持續的過程中，一旦出現與上述結論相悖的情況，就說明此數不是二叉搜索樹
如果最后size為0了，則說明此樹為二叉所搜樹。

class Solution {
public:bool VerifySquenceOfBST(vector<int> sequence) {int size = sequence.size(); //求出數組長度if(0==size)                //為0返回return false;int i = 0;//去掉總根結點后，數組最后一個元素就是右子樹的根結點，它的左子樹都比它小，右子樹都比它大//那么size再--，就到了右子樹的右子樹或者到左子樹，上述條件仍然成立while(--size){while(sequence[i++]<sequence[size]); //看左子樹的值是不是都小于根結點while(sequence[i++]>sequence[size]); //右子樹的值是不是都大于根結點if(i<size) //如果最后i還沒有和size相同，返回錯誤return false;i = 0;}return true;}
};