題目描述

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

解題思路

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

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

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

總結(jié)

以上是生活随笔為你收集整理的【剑指offer】_09二叉搜索树的后序遍历序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。