問題描述：

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

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

背景知識：

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

算法描述：

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

    | 小于根 | 大于根 | 根 |

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

    當(dāng)樹的大小為0或1時，返回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;        }        //開始切割數(shù)列        vector<int>smaller;  //第一段，比root小        vector<int>larger;       //第二段，比root大        //根的值        introot = sequence[size - 1];        //判斷此時是否還在第一段，若已經(jīng)在第二段，但又回到了第一段        //則返回false        bool isOne = false;        //如果第一個數(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)該多弄點測試用例，自己測試完后，再提交