問(wèn)題描述：

    輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果，

[劍指Offer]二叉搜索樹(shù)的后序遍歷序列

背景知識(shí)：

    二叉搜索樹(shù)（Binary Search Tree），又叫二叉排序樹(shù)：或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)： 若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹(shù)也分別為二叉排序樹(shù)。

算法描述：

    將數(shù)列分為三段，最后一段是最后一個(gè)數(shù)，也是樹(shù)的根；第一段小于根，第二段大于根：

    | 小于根 | 大于根 | 根 |

    然后小于根和大于根這兩段又都是樹(shù)，就可以遞歸求解了。

    當(dāng)樹(shù)的大小為0或1時(shí)，返回true。

代碼：

<code class="hljs" cpp="">classSolution {public:    bool VerifySquenceOfBST(vector<int>sequence) {        if(sequence.size() == 0) {            return false;        }        returnVerify(sequence);    }    bool Verify(vector<int>sequence) {        intsize = sequence.size();        if(size <= 1) {            return true;        }        //開(kāi)始切割數(shù)列        vector<int>smaller;  //第一段，比root小        vector<int>larger;       //第二段，比root大        //根的值        introot = sequence[size - 1];        //判斷此時(shí)是否還在第一段，若已經(jīng)在第二段，但又回到了第一段        //則返回false        bool isOne = false;        //如果第一個(gè)數(shù)小于root，則表明有第一段，isOne為true        if(sequence[0] < root) {            isOne = true;        }        for(inti = 0; i < size - 1; i++) {            //比根小            if(sequence[i] < root) {                if(isOne == false) {                    returnfalse;                }                smaller.push_back(sequence[i]);            }            //比根大            else{                if(isOne)                    isOne = false;                larger.push_back(sequence[i]);            }        }        returnVerify(smaller) && Verify(larger);    }};</int></int></int></int></code>

    總結(jié)：

    應(yīng)該多弄點(diǎn)測(cè)試用例，自己測(cè)試完后，再提交