判断序列是否是二叉搜索树的后续遍历
判断是否要从二叉树的定义着手:
- 根节点大于所有左子树上的节点,小于右子树所有节点;
- 子树递归满足此条件
注:既然是搜索树,那么认为无重复节点(无相同关键字)
function test(a, l, r)
{
if(l == r) return true;
let root = a[r];
let i = l;
while(a[i] < root) i++;
let mid = i;
while(i < r){
if(a[i] < root) return false;
i++;
}
let flag = true;
if(mid > l){
flag = flag && test(a, l, mid - 1);
}
if(mid <= r){
flag = flag && test(a, mid, r - 1);
}
return flag;
}
// let a = [5, 7, 6, 9, 11, 10, 8];
let a = [7, 4, 6, 5];
let valid_post_order_tree = test(a, 0, a.length - 1);
console.log(valid_post_order_tree);
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: