题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
思路
递归：根结点为数组最后一个元素，找到第一个大于根节点的元素，以此划分左右子树。验证左（右）子树节点是否全部小于（大于）根结点，再递归验证左右子树是否为二叉搜索树。
要点
递归终止条件：i >= j，验证到叶子结点或该区间没有节点，直接返回true
递归工作：
划分左右子树： 遍历[i,j-1]区间，直到找到第一个大于root的元素，索引记为m。则[i, m-1]属于左子树，[m, j]属于右子树。
PS: 若没有左子树，即所有元素都大于root，则m===i, 下一层递归时左子树recursion(i, i-1)会出现 i > j， 所以终止条件是>=不是===
若没有右子树，即所有元素都小于root，则m===j，下一层递归recursion(i, j-1)和recursion(j, j)
判断是否为二叉搜索树：
左子树[i, m-1]所有节点都小于root，第一步划分左右子树时已验证过
右子树[m,j−1] 所有节点都应大于root, while循环遍历检查，若在验证到j-1之前提前退出则不满足。
另一种描述：可以理解为遍历[i, j-1]的每一个节点，逐个验证与根节点的大小关系，在第一比根节点大的元素之后的所有元素必须全部大于根节点。
代码
/** * @param {number[]} postorder * @return {boolean} */ var verifyPostorder = function(postorder) { if(!postorder || !postorder.length) return true; return recursion(0, postorder.length-1); function recursion(i, j){ if(i >= j) return true; const root = postorder[j]; let verifyP = i; //划分左右子树 + 验证左子树是否全部小于root while(verifyP < j && postorder[verifyP]<root){ verifyP++; } //记录右子树起点 let rightStart = verifyP; //验证右子树是否全部大于root while(verifyP < j && postorder[verifyP]>root){ verifyP++; } if(verifyP !== j){ return false; } return recursion(i, rightStart-1) && recursion(rightStart, j-1); } };
原文：https://www.cnblogs.com/xintangchn/p/13190121.html