建站
咨詢
售后
建站咨詢
新聞中心
前言
有一個整數(shù)數(shù)組，如何判斷該數(shù)組是不是某個二叉樹的后序遍歷結果？本文就跟大家分享下這個算法，歡迎各位感興趣的開發(fā)者閱讀本文。
創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設、高性價比東湖網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式東湖網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設找我們，業(yè)務覆蓋東湖地區(qū)。費用合理售后完善，十載實體公司更值得信賴。
思路分析
我們通過一個例子來分析這個問題，如下所示為一顆二叉樹。
通過之前文章的學習（二叉樹的后序遍歷），我們可以很快看出這顆樹的后序遍歷序列為: [5, 7, 6, 9, 11, 10, 8]，通過觀察后我們發(fā)現(xiàn)最后一個數(shù)字為二叉樹的根節(jié)點，數(shù)組中前面的數(shù)字可以分為兩部分：
第一部分是左子樹節(jié)點的值，它們都比根節(jié)點的值小
第二部分是右子樹節(jié)點的值，它們都比根節(jié)點的值大
在上面的后序遍歷結果數(shù)組中，前3個數(shù)字5、7、6?都比根節(jié)點8小，是它的左子樹節(jié)點；后3個數(shù)字9、11、10都比根節(jié)點8大，是它的右子樹節(jié)點。
那么，我們就可以用同樣的方法來確定數(shù)組每一部分對應的子樹的結構。
數(shù)組5, 7, 6，最后一個數(shù)字6是左子樹的根節(jié)點的值。數(shù)字5比6小，是6的左子節(jié)點，7則是它的右子節(jié)點
數(shù)組9, 11, 10，最后一個數(shù)字10是左子樹的根節(jié)點的值。數(shù)字9比10小，是10的左子節(jié)點，11則是它的右子節(jié)點
實現(xiàn)思路
通過上面的分析，我們便可以總結出實現(xiàn)思路了。
最后一項一定是根節(jié)點，從根節(jié)點前面的值中尋找左、右子樹的分界點
定義指針leftIndex，前半部分一定是它的左子樹，每個節(jié)點的值都比根節(jié)點小
leftIndex默認從0開始，逐漸遞增，尋找比根節(jié)點大的值，便是它們的分界點
定義指針rightIndex，后半部分一定是它的右子樹，每個節(jié)點的值都比根節(jié)點大。
rightIndex從分界點開始找（默認從leftIndex位置開始），如果有比根節(jié)點小的值，那么這個序列一定不屬于二叉樹的后序遍歷序列
如果leftIndex指針離開了起始位置（0），證明它的左子節(jié)點還沒找完，需要重復執(zhí)行上述過程繼續(xù)查找（遞歸尋找到數(shù)組的leftIndex位置）
如果leftIndex指針沒有到達數(shù)組末尾，證明它的右子節(jié)點還沒找完，需要重復執(zhí)行上述過程繼續(xù)查找（從leftIndex+1位置開始遞歸）
返回左、右子樹的遞歸校驗結果（兩者都為true則表示這個序列為二叉樹的后序遍歷序列）
實現(xiàn)代碼
捋清楚思路后，我們便可以順利的寫出代碼了。
verifySequenceOfBST(sequence: Array, length: number): boolean {
if (sequence == null || length <= 0) return false;
const root = sequence[length - 1];
// 左子樹節(jié)點的值小于根節(jié)點的值
let leftIndex = 0;
for (; leftIndex < length - 1; leftIndex++) {
if (sequence[leftIndex] > root) {
break;
}
}
// 右子樹節(jié)點的值大于根節(jié)點的值
let rightIndex = leftIndex;
for (; rightIndex < length - 1; rightIndex++) {
if (sequence[rightIndex] < root) {
return false;
}
}
// 判斷左子樹是否為二叉樹
let leftVerify = true;
if (leftIndex > 0) {
leftVerify = this.verifySequenceOfBST(sequence, leftIndex);
}
let rightVerify = true;
if (leftIndex < length - 1) {
rightVerify = this.verifySequenceOfBST(
sequence.slice(leftIndex + 1),
length - leftIndex - 1
);
}
return leftVerify && rightVerify;
}
測試用例
接下來我們將思路分析中所列舉的例子代入上述代碼，來驗證下我們的代碼能否正確執(zhí)行。
const arr = [5, 7, 6, 9, 11, 10, 8];
console.log("比對結果", treeOperateTest.verifySequenceOfBST(arr, arr.length));
我們再列舉一個錯誤的例子，來驗證下它能否正確判斷。
const arr = [7, 4, 6, 5];
console.log("比對結果", treeOperateTest.verifySequenceOfBST(arr, arr.length));
示例代碼
本文用到的代碼完整版請移步：
- TreeOperate.ts
- TreeOperate-test.ts
當前標題：二叉樹的后序遍歷序列
標題網(wǎng)址：http://www.5511xx.com/article/dpchejj.html
