题目

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

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

示例 1：

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

示例 2：

输出: [1,3,2,6,5]
输入: true

准备知识点

二叉树的遍历

二叉树的深度优先遍历可细分为前序遍历、中序遍历、后序遍历，这三种遍历能够用递归实现，也可应用非递归实现。

前序遍历：根节点->左子树->右子树（根->左->右）

中序遍历：左子树->根节点->右子树（左->根->右）

后序遍历：左子树->右子树->根节点（左->右->根）

1. 前序遍历

前序的遍历的特点，根节点->左子树->右子树，留神看前序的遍历的代码printf语句是放在两条递归语句之前的，所以先拜访根节点G，打印G，而后拜访左子树D，此时左子树D又作为根节点，打印D，再拜访D的左子树A

A又作为根节点，打印A，A没有左子树或者右子树，函数调用完结返回到D节点（此时曾经打印进去的有：GDA）D节点的左子树曾经递归实现，当初递归拜访右子树F，F作为根节点，打印F，F有左子树拜访左子树E，E作为

根节点，打印E，（此时曾经打印进去的有：GDAFE），E没有左子树和右子树，函数递归完结返回F节点，F的左子树曾经递归实现了，但没有右子树，所以函数递归完结，返回D节点，D节点的左子树和右子树递归全副实现，

函数递归完结返回G节点，拜访G节点的右子树M，M作为根节点，打印M，拜访M的左子树H，H作为根节点，打印H，（此时曾经打印进去的有：GDAFEMH）H没有左子树和右子树，函数递归完结，返回M节点，M节点的左子树曾经

递归实现，拜访右子树Z，Z作为根节点，打印Z，Z没有左子树和右子树，函数递归完结，返回M节点，M节点的左子树右子树递归全副实现，函数递归完结，返回G节点，G节点的左右子树递归全副实现，整个二叉树的遍历就完结了

前序遍历后果：GDAFEMHZ

总结一下前序遍历步骤

第一步：打印该节点

第二步：拜访左子树，返回到第一步（留神：返回到第一步的意思是将根节点的左子树作为新的根节点，就好比图中D是G的左子树然而D也是A节点和F节点的根节点）

第三步：拜访右子树，返回到第一步

第四步：完结递归，返回到上一个节点

前序遍历的另一种表述：

（1）拜访根节点

（2）前序遍历左子树

（3）前序遍历右子树

（在实现第2,3步的时候，也是要依照前序遍历二叉树的规定实现）

2. 中序遍历（具体遍历过程就不再赘述了，(┬＿┬)）

第一步：拜访该节点左子树

第二步：若该节点有左子树，则返回第一步，否则打印该节点

第三步：若该节点有右子树，则返回第一步，否则完结递归并返回上一节点

（按我本人了解的中序就是：先左到底，左到不能在左了就停下来并打印该节点，而后返回到该节点的上一节点，并打印该节点，而后再拜访该节点的右子树，再左到不能再左了就停下来）

中序遍历的另一种表述：

（1）中序遍历左子树

（2）拜访根节点

（3）中序遍历右子树

（在实现第1，3步的时候，要依照中序遍历的规定来实现）

所以该图的中序遍历为：ADEFGHMZ

3. 后序遍历步骤

第一步：拜访左子树

第二步：若该节点有左子树，返回第一步

第三步：若该节点有右子树，返回第一步，否则打印该节点并返回上一节点

后序遍历的另一种表述：

（1）后序遍历左子树

（2）后序遍历右子树

（3）拜访根节点

（在实现1,2步的时候，仍然要依照后序遍历的规定来实现）

该图的后序遍历为：AEFDHZMG

网上多找一些重构二叉树的练习题，有助于加深了解上述三种遍历树的过程

重要概念

二叉搜寻树特色：左子树小于根节点小于右子树

题解思路

了解上述知识点后，回顾题目，既然是后序遍历，那么，数组最初一个肯定是根节点，例如给你[1,3,2,6,5]这个数组，那么5就是根节点，依照二叉搜寻树的特色，1，3就是左子树，2，6，5就是右子树。同时每个子树也要满足上诉条件，自然而然就想到递归查找判断了。明确了这些原理后，用代码实现就很容易了。

代码实现

/** * @param {number[]} postorder * @return {boolean} */var verifyPostorder = function(postorder) {    if (!postorder.length) return true; // 如果没有子树了，返回true    const root = postorder[postorder.length - 1]; // 后续遍历后果的最初一位是树的根节点    // 根节点的左子树全副小于根节点，根节点的右子树全副大于根节点    const leftTree = [], rightTree = []; // 缓存以后节点的左子树和右子树，用于下次递归查问判断    let cIndex = null; // 记录左右子树的分界点，即第一个满足右子树的节点，因为左右子树要离开递归查    const flag = postorder.every((item, index) => {        if (index === postorder.length - 1) return true; // 根节点不判断        if (cIndex === null && item > root) {            cIndex = index; // 记录第一个遇到大于根节点的右子树节点，作为分界线        }        if (cIndex !== null) { // 如果cIndex !== null，阐明曾经遍历到右子树的节点了，那就要依照右节点的规定判断接下去的树（右子树的值全都要大于根节点），并且把之后的节点push到右子树的数组，用于递归            if (index >= cIndex) {                rightTree.push(item);                return item > root;            }        } else {  // 如果cIndex === null就说名没有遇到右子树的节点，那就判断左子树的特色，左子树的节点都要小于根节点            leftTree.push(item);            return item < root;        }    })    if (!flag) return false; // 以后节点都没有满足搜寻的特色，那就间接返回false了    let left = true, right = true;    if (leftTree.length) {        left = verifyPostorder(leftTree); // 递归查问判断左子树是否满足二叉搜寻树的特色    }     if (rightTree.length) {        right = verifyPostorder(rightTree); // 递归查问判断右子树是否满足二叉搜寻树的特色    }    return left && right; // 左右都满足二叉搜寻树的特色，才会返回true};