【leecode 剑指offer】二叉搜索树的后序遍历序列

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

题目

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

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

解题思路

1. 后续遍历是左右根。因此postorder的顺序是左子树+右子树+根。
2. 二叉搜索树的性质是，左子树都比根节点小，右子树都比根节点大。并且每个节点（除叶子节点）都符合这个情况。
3. 因此检查左子树是否都小于根节点，右子树是否都大于根节点。并递归检查每个子树。都符合返回true

算法展示

/*** @param {number[]} postorder* @return {boolean}*/
var verifyPostorder = function(postorder) {
    //搜索二叉树特点，左子树里的节点<根节点<右子树节点if(postorder.length<=2) return true;let root = postorder.pop();let i = 0;// 找到左右节点的分界点，且保证左子树节点都小于根节点while(postorder[i]<root){
    i++;}// 判断右子树所有节点是否都大于根节点const res = postorder.slice(i).every(item=> item>root);// 递归判断左右子树return res&& verifyPostorder(postorder.slice(0,i))&&verifyPostorder(postorder.slice(i));};