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

思路

后序遍历是按左子节点、右子结点、自己的顺序来遍历的，因此在一段序列中最后一个就是根节点。
找到了根节点，我们可以把后序遍历序列划分成两部分，即【小于根节点的子序列】、【大于根节点的子序列】，即【左子树后序遍历序列】、【右子树后序遍历序列】。
而按照二叉搜索树的定义，左子树都小于根节点，右子树都大于根节点，因此这里产生了判断条件，【左子树后序遍历序列】中所有元素都要小于根节点值，而【右子树后序遍历序列】中所有元素都要大于根节点值，否则该序列不合理。
使用递归方法，判断完了本层，再递归判断【左子树后序遍历序列】、【右子树后序遍历序列】。
特殊值：

• 最初的序列若为空，因为约定空树不是二叉树，所以返回false.
• 在递归函数中，如果子序列是空/子序列只有一个/子序列有两个值，都返回true。
• 递归函数中，子序列剥离出来的只有左子树，则直接判断该序列是否合理即可。

代码

function VerifySquenceOfBST(sequence)
{
    // write code here
  if(sequence.length === 0) return false;
  return check(sequence);
}

function check(sequence){
  let len = sequence.length;
  if(len <= 2) return true;
  let root = sequence[len - 1];
  let x = -1;
  for(let i = 0; i < len - 1; i++){
    if(sequence[i] > root){
      x = i;
      break;
    }
  }
  if(x === -1) return check(sequence.slice(0, len-1));
  let left = sequence.slice(0, x);
  let right = sequence.slice(x, len - 1);
  let f1 = left.every(cur => cur<root);
  let f2 = right.every(cur => cur>root);
  return f1 && f2 && check(left) && check(right);
}

module.exports = {
    VerifySquenceOfBST : VerifySquenceOfBST
};