判断序列是否是二叉搜索树的后续遍历

判断是否要从二叉树的定义着手：

1. 根节点大于所有左子树上的节点，小于右子树所有节点；
2. 子树递归满足此条件

注：既然是搜索树，那么认为无重复节点（无相同关键字）

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 协议》，转载必须注明作者和本文链接