二叉树的后序遍历序列

  verifySequenceOfBST(sequence: Array<number>, length: number): boolean {
    if (sequence == null || length <= 0) return false;
    const root = sequence[length - 1];
    // 左子树节点的值小于根节点的值
    let leftIndex = 0;
    for (; leftIndex < length - 1; leftIndex++) {
      if (sequence[leftIndex] > root) {
        break;
      }
    }
    // 右子树节点的值大于根节点的值
    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;
  }

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));