//比如一个二叉树
// 4
// 2 6
// 1 3 5 7
//其后序遍历为[1,3,2,5,7,6,4]
//length为7，起始时sequence.length-1=6
function VerifySquenceOfBST(sequence)
{
// write code here
if(sequence.length<=0) return;
return test(sequence,0,sequence.length-1)
}
function test(sequence,start,end){
if(start>=end) return true;//空树也是搜索二叉树
var i=end-1;//第一次执行test时end的位置上一定是整个二叉树的根节点
//将数组[1,3,2,5,7,6,4]分为小于根节点4的部分和大于4的部分
//大于4的部分一定是4的右子树，小于4的部分是左子树
//从4的前一位开始与4比较，只要比4大，就继续向前一位移动，最后i==2，此为为数字2，正好比4小
while(i>=start&&sequence[i]>sequence[end]){
i--;
}
//判断从第2位再往前的位是否都比4小，如果任意一位大于4，则肯定不是搜索二叉树
for(var j=i;j>=start;j--){
if(sequence[j]>sequence[end]){
return false;
}
}
//对root的左子树重新当成一颗树进行递归判断；
//对root的右子树重新当成一棵树进行递归判断；
//左右子树都满足搜索二叉树条件时即整棵树都为搜索二叉树
return test(sequence,start,i)&&test(sequence,i+1,end-1)
}
第23题-二叉搜索树的后序遍历序列【JavaScript】
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
