js剑指提供23个二进制搜索树的后序遍历序列

输入一个整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

const VerifySquenceOfBST = sequence => {
    if(!sequence.length) return false;
    return test(sequence, 0, sequence.length - 1);
};
var test = (data, start, end) => {
    if(start >= end) return true;
    let i = end - 1;
    while(i >= start && data[i] > data[end]) i--;
    for(let j = i; j >= start; j--){
        if(data[j] >= data[end]) return false;
    }
    return test(data, start, i) && test(data, i, end - 1);
}

二进制搜索树: 也称为二进制搜索树二叉排序树 遍历，二进制排序树.

它是具有以下属性的空树或二叉树:

如果其左子树不为空，则左子树上所有节点的值小于其根节点的值；如果其右子树不为空，则右子树上所有节点的值都大于其根节点的值;它的左和右子树也是二叉排序树.

二进制搜索树按顺序遍历相应的数组，并且最后一个元素必须是与节点相对应的元素. 根据二叉查找树的性质，正确单词的所有数字都应大于他，因此请从后到前查找比率. 具有小根节点的元素的位置理论上是左子树. 遍历左子树的所有元素，如果数据多于根节点，则肯定与标题不一致. 如果不是二叉排序树 遍历，请分别测试左子树以确定它是否是二进制排序树.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-251428-1.html