《劍指offer》面試題24：

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

分析： 分析輸入是整數數組，而不是整數數組和二叉樹，所以不是說后序遍歷一下二叉樹與數組數組比較來判斷是否是此二叉樹的后序遍歷序列。

??????????? 而是判斷輸入的整數數組是否是某一課二叉樹的后序遍歷序列的結果，如輸入數組為{4, 8, 6, 12, 16, 14, 10}，則返回true，因為序列是如下圖數的后序遍歷結果；

?????????? 而輸入數組{7, 4, 6, 5}，則由于沒有二叉樹與此序列對應，則返回false。

????????? 由于后序遍歷得到的序列中，最后一個數字是二叉樹的根結點的值。數組前面的數字可以分成兩部分：左子樹部分和右子樹部分。左子樹的數據值都小于根結點的值，右字數的數據值都大于根結點的值。采用遞歸的方法，從頭掃描序列找到第一個大于根結點值的數，此數之前的值都為左子樹部分，此數之后到最后一個數字前都是右子樹部分，如果右子樹部分出現小于根結點值的值則不符合規則，即返回false。否則遞歸左右子樹。

（1） 自己寫的代碼：注意當查找的序列只有一個或者兩個時，肯定是某個二叉樹的后序序列；當查找的序列三個及以上時，查找到分割點時需要判斷分割點的值，注意不要越界。

bool IsPostTraverseOfBST(const int sequence[], int length) {if(sequence == NULL || length <= 0)return false;return IsPostTraverseOfSubBST(sequence,0,length-1);} bool IsPostTraverseOfSubBST( const int sequence[], int start, int end ) {if( end - start <0 ){return false;}//only 1 or 2 elementsif( end - start <= 1){return true;}int rootData = sequence[end];int index = start;// find the left subtreefor( ; index <= end-1; ++index ){if( sequence[index] > rootData ){break;}}// find the right subtree int midIndex = index++ ;for( ; index<=end-1; ++index ){if( sequence[index]<rootData ){return false;}}bool isLeft = true;if( midIndex > 0 ){isLeft = IsPostTraverseOfSubBST( sequence,start, midIndex-1);}bool isRight = true;if( midIndex < end ){isRight = IsPostTraverseOfSubBST( sequence,midIndex,end-1 );}return isLeft&&isRight; }

（2）附上《劍指offer》中示例代碼

bool VerifySquenceOfBST(int sequence[], int length) {if(sequence == NULL || 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 = VerifySquenceOfBST(sequence, i);// 判斷右子樹是不是二叉搜索樹bool right = true;if(i < length - 1)right = VerifySquenceOfBST(sequence + i, length - i - 1);return (left && right); }



總結

以上是生活随笔為你收集整理的面试题整理7 二叉搜索树的后序遍历序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。