二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
二叉搜索树的特点：某一个节点左子树的所有节点的值都比该节点小，右子树的所有节点的值都比该节点大
依次与数组最后一个值比较，一直小于最后一个数的是左子树的，计数，剩下的是右子树的，依次判断剩下的是否全部大于最后一个数，若否，则为false。
使用递归，依次判断每一个子数组是否满足上一个条件
小技巧：将返回true的条件由s==e改为s>=e，则无需判断是否有lessE == s || lessE == e，直接return judge(arr,s,lessE-1) && judge(arr,lessE,e-1)即可。（否则会出现s<e的情况）
代码
function VerifySquenceOfBST(sequence
)
{
function judge(sequence
,sta
,end
){
if(sta
>= end
){
return true;
}
var i
= end
;
while(i
> sta
&& sequence
[i
-1] > sequence
[end
]){
--i
;
}
for(var j
= i
- 1;j
>= sta
; --j
){
if(sequence
[j
] > sequence
[end
]){
return false;
}
}
return judge(sequence
,sta
,i
- 1)&&(judge(sequence
,i
,end
-1));
}
if (!sequence
.length
) {
return false;
}
return judge(sequence
, 0, sequence
.length
- 1);
}
