題目描述：輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷結果。如果是則返回true,否則返回false。假設輸入的數組的任意兩個數字都互不相同。例如，輸入數組{5,7,6,9,11,10,8},則返回true,，因為這個整數是下圖二叉搜索樹的后序遍歷結果，如果輸入的數組是{7,4,6,5},則由于沒有哪棵二叉搜索樹的后序遍歷結果是這個序列，因此返加false。
二叉搜索樹是一種二叉樹的樹形數據結構，其定義如下：
-
空樹是二叉搜索樹。
-
若二叉搜索樹的左子樹不為空，則其左子樹上所有點的附加權值均小于其根節點的值。
-
若二叉搜索樹的右子樹不為空，則其右子樹上所有點的附加權值均大于其根節點的值。
-
二叉搜索樹的左右子樹均為二叉搜索樹。
?
分析：后序遍歷得到的序列，最后一個數字是樹的根節點的值。數組中前面的數字可以分為兩部分：第一部分是左子樹節點的值，它們都比根節點的值小;第二部分是右子樹節點的值，它們都比根節點的值大。接下來可以遞歸確定與數組每一部分對應的子樹的結構。
bool VerifySquenceOfTree(int sequence[],int length){if(sequence == nullptr || length <= 0)return false;int root = sequence[length - 1];//在二叉樹搜索樹中左子樹節點的值小于根節點的值int i = 0;for(;i < length - 1;++i){if(sequence[i] > root)break;}//在二叉搜索樹中右子樹節點的值都大于根節點的值int j = i;for(;j < length - 1;++j){if(sequence[j] < root)return false; //如果右子樹節點的值小于根節點的值則不滿足}//判斷左子樹是不是二叉搜索樹bool left = true;if(i > 0)left = VerifySquenceOfTree(sequence,i);//判斷右子樹是不是二叉搜索樹bool right = true;if(i < length - 1)right = VerifySquenceOfTree(sequence + i,length - i - 1);return (left && right);
}
