题目描述：

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

参考以下这颗二叉搜索树：

  1.  5<br />    / \<br />   2   6<br />  / \<br /> 1   3<br />示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof

解题思路：

  • 这道题和24.重建二叉树的思路很像，其主要考察的是对先序遍历与中序遍历的理解，我们知道，先序遍历的第一个节点为根节点，根节点将中序遍历分为了左右子树。
  • 而这道题主要考察我们对后序遍历的理解，我们同样可以知道后序遍历的最后一个节点为根节点，根节点将遍历数组分为左右子树，那么我们如何找到左右子树呢？
  • 通过我们的观察可以发现，其左子树一定是小于根节点的，右子树是大于根节点的，所以我们不断递归判断便好，当访问到根节点时返回true

解题代码：

var verifyPostorder = function(postorder) {
    if(!postorder.length) return true; // 注意如果数组为空则证明是后序遍历
    let root = postorder.pop();
    let i = 0;
    for(;i<postorder.length;i+=1) {
        if(postorder[i] > root) {
            break;
        }
    };
    let res = postorder.slice(i).every((n) => n > root);
    if(res) {
        return verifyPostorder(postorder.slice(0,i)) &&  
        verifyPostorder(postorder.slice(i))
    }else {
        return false;
    }
};