前言

有一個(gè)整數(shù)數(shù)組，如何判斷該數(shù)組是不是某個(gè)二叉樹(shù)的后序遍歷結(jié)果？本文就跟大家分享下這個(gè)算法，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。

思路分析

我們通過(guò)一個(gè)例子來(lái)分析這個(gè)問(wèn)題，如下所示為一顆二叉樹(shù)。

通過(guò)之前文章的學(xué)習(xí)（二叉樹(shù)的后序遍歷），我們可以很快看出這顆樹(shù)的后序遍歷序列為: [5, 7, 6, 9, 11, 10, 8]，通過(guò)觀察后我們發(fā)現(xiàn)最后一個(gè)數(shù)字為二叉樹(shù)的根節(jié)點(diǎn)，數(shù)組中前面的數(shù)字可以分為兩部分：

第一部分是左子樹(shù)節(jié)點(diǎn)的值，它們都比根節(jié)點(diǎn)的值小

第二部分是右子樹(shù)節(jié)點(diǎn)的值，它們都比根節(jié)點(diǎn)的值大

在上面的后序遍歷結(jié)果數(shù)組中，前3個(gè)數(shù)字5、7、6?都比根節(jié)點(diǎn)8小，是它的左子樹(shù)節(jié)點(diǎn)；后3個(gè)數(shù)字9、11、10都比根節(jié)點(diǎn)8大，是它的右子樹(shù)節(jié)點(diǎn)。

那么，我們就可以用同樣的方法來(lái)確定數(shù)組每一部分對(duì)應(yīng)的子樹(shù)的結(jié)構(gòu)。

數(shù)組5, 7, 6，最后一個(gè)數(shù)字6是左子樹(shù)的根節(jié)點(diǎn)的值。數(shù)字5比6小，是6的左子節(jié)點(diǎn)，7則是它的右子節(jié)點(diǎn)

數(shù)組9, 11, 10，最后一個(gè)數(shù)字10是左子樹(shù)的根節(jié)點(diǎn)的值。數(shù)字9比10小，是10的左子節(jié)點(diǎn)，11則是它的右子節(jié)點(diǎn)

實(shí)現(xiàn)思路

通過(guò)上面的分析，我們便可以總結(jié)出實(shí)現(xiàn)思路了。

最后一項(xiàng)一定是根節(jié)點(diǎn)，從根節(jié)點(diǎn)前面的值中尋找左、右子樹(shù)的分界點(diǎn)

定義指針leftIndex，前半部分一定是它的左子樹(shù)，每個(gè)節(jié)點(diǎn)的值都比根節(jié)點(diǎn)小

leftIndex默認(rèn)從0開(kāi)始，逐漸遞增，尋找比根節(jié)點(diǎn)大的值，便是它們的分界點(diǎn)

定義指針rightIndex，后半部分一定是它的右子樹(shù)，每個(gè)節(jié)點(diǎn)的值都比根節(jié)點(diǎn)大。

rightIndex從分界點(diǎn)開(kāi)始找（默認(rèn)從leftIndex位置開(kāi)始），如果有比根節(jié)點(diǎn)小的值，那么這個(gè)序列一定不屬于二叉樹(shù)的后序遍歷序列

如果leftIndex指針離開(kāi)了起始位置（0），證明它的左子節(jié)點(diǎn)還沒(méi)找完，需要重復(fù)執(zhí)行上述過(guò)程繼續(xù)查找（遞歸尋找到數(shù)組的leftIndex位置）

如果leftIndex指針沒(méi)有到達(dá)數(shù)組末尾，證明它的右子節(jié)點(diǎn)還沒(méi)找完，需要重復(fù)執(zhí)行上述過(guò)程繼續(xù)查找（從leftIndex+1位置開(kāi)始遞歸）

返回左、右子樹(shù)的遞歸校驗(yàn)結(jié)果（兩者都為true則表示這個(gè)序列為二叉樹(shù)的后序遍歷序列）

實(shí)現(xiàn)代碼

捋清楚思路后，我們便可以順利的寫(xiě)出代碼了。

  verifySequenceOfBST(sequence: Array<number>, length: number): boolean {
    if (sequence == null || length <= 0) return false;
    const root = sequence[length - 1];
    // 左子樹(shù)節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值
    let leftIndex = 0;
    for (; leftIndex < length - 1; leftIndex++) {
      if (sequence[leftIndex] > root) {
        break;
      }
    }
    // 右子樹(shù)節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值
    let rightIndex = leftIndex;
    for (; rightIndex < length - 1; rightIndex++) {
      if (sequence[rightIndex] < root) {
        return false;
      }
    }

    // 判斷左子樹(shù)是否為二叉樹(shù)
    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è)試用例

接下來(lái)我們將思路分析中所列舉的例子代入上述代碼，來(lái)驗(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ò)誤的例子，來(lái)驗(yàn)證下它能否正確判斷。

const arr = [7, 4, 6, 5];
console.log("比對(duì)結(jié)果", treeOperateTest.verifySequenceOfBST(arr, arr.length));

示例代碼

本文用到的代碼完整版請(qǐng)移步：

• TreeOperate.ts
• TreeOperate-test.ts