题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
分析
所谓二叉搜索树，也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
那么对于二叉搜索树的后序遍历的序列来说，最后一个元素即是它的根节点，序列的前某部分元素全部小于最后一个元素，序列的后某部分元素全大于最后一个元素。然后对于这两部分来说，又分别符合这些特点，可以递归的检查下去。
递归实现
function VerifySquenceOfBST(s) { if(s.length === 0) return false; return judge(s, 0, s.length-1); } function judge(a, l, r) { if(l >= r) return true; var p1 = r; while(p1 > l && a[p1-1] > a[r]) { p1--; } var p2 = p1-1; while(p2 >= l){ if(a[p2] > a[r]) return false; p2--; } return judge(a, l, p1-1) && judge(a, p1, r-1); } 复制代码
非递归实现
对于一个二叉搜索树来说，根节点的左子树每个节点的值肯定小于右子树每个节点的值，所以可以不断的去去掉序列的最后一个值，并且把剩下的部分分成小于最后一个值和大于最后一个值的两部分，只要能分出来那就说明符合二叉搜索树的定义，否则就不符合。
function VerifySquenceOfBST(s) { if(s.length === 0) return false; var start = 0, end = s.length-1; while(end !== 0) { while(s[start] < s[end]){ start++; } while(s[start] > s[end]){ start++; } if(start < end) return false; end--; start = 0; } return true; }
