前言

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

思路分析

我們通過一個例子來分析這個問題，如下所示為一顆二叉樹。

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

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

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

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

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

數(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)思路

通過上面的分析，我們便可以總結(jié)出實現(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位置開始遞歸）

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

實現(xiàn)代碼

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

  verifySequenceOfBST(sequence: Array<number>, 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("比對結(jié)果", treeOperateTest.verifySequenceOfBST(arr, arr.length));

我們再列舉一個錯誤的例子，來驗證下它能否正確判斷。

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

示例代碼

本文用到的代碼完整版請移步：

• TreeOperate.ts
• TreeOperate-test.ts