题解 | #二叉搜索树的后序遍历序列#

function VerifySquenceOfBST(sequence) {
  // write code here
  if (sequence.length === 0) return false
  if (sequence.length < 3) return true;
  const root = sequence[sequence.length - 1]

  let leftEnd = 0
  while (sequence[leftEnd] < root) {
      leftEnd++
  }
  let rightStart = sequence.length - 2
  while (sequence[rightStart] > root) {
      rightStart --
  }
  if (leftEnd - 1 !== rightStart) {
    return false
  } else {
      const left = sequence.slice(0, leftEnd)
      const right = sequence.slice(leftEnd, sequence.length - 1)
      return (left.length === 0 || VerifySquenceOfBST(left)) && (right.length === 0 || VerifySquenceOfBST(right))
  }
}
module.exports = {
  VerifySquenceOfBST: VerifySquenceOfBST,
};