二叉搜索树的后序遍历序列

《剑指offer》刷题笔记。如有更好解法，欢迎留言。

关键字：树

题目描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：

二叉搜索树后序遍历的特点：

• 最后一个一定是root
• 左子树所有节点都比根小
• 右子树所有节点都比根大

检查输入的数组是否符合上述特点

• 获取根节点let root = sequence[sequence.length-1];
• 遍历数组，小于 root 的部分为左子树，其中 index 分割左右子树。

    let index = 0;
    for(let i = 0;i < sequence.length-1;i++){
        if(root > sequence[i]){
            index++;
        }
    }

• 检查右子树中是否全部大于 root ，不符合直接返回 false

    for(let j = index;j < sequence.length-1;j++){
      if(root > sequence[j]){
        return false;
      }
    }

• 递归检查左右子树。

  
  

• 完整代码

function VerifySquenceOfBST(sequence)
{
    if(sequence.length === 0){
        return false;
    }
    let root = sequence[sequence.length-1];
    let index = 0;
    for(let i = 0;i < sequence.length-1;i++){
        if(root > sequence[i]){
            index++;
        }
    }
    for(let j = index;j < sequence.length-1;j++){
      if(root > sequence[j]){
        return false;
      }
    }
    let left = sequence.slice(0,index);
    let right = sequence.slice(index,sequence.length-1);
    (left.length > 0) && VerifySquenceOfBST(left);
    (right.length > 0) && VerifySquenceOfBST(right);
    return true;
}