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