SOURCE

// 思路
// 二叉查找树：特点是所有左节点比父节点的值小 所有右节点比父节点的值大
// 既然是以二叉树结构遍历检查数组 因此以递归的思路每次将当前片段的数组截成两段
// 并在递归时记录下一段左子树的最大值 右子树的最小值
// 以此作为判断是否符合二叉查找树的依据 并以片段的起始位置大于结束位置作为递归出口
// 注 js中 逻辑运算符 为短路运算 如&&是找false 只要找到第一个运算结果为false的就停下
// 并返回其结果(本题是false) 如果没找到false 则返回最后一个表达式运算结果(本题是true)

function fn(arr) {
    // 递归检查子树是否满足前序遍历特性
    function 判断(arr, start, end, min, max) {
        // 每次递归都会向后移动start
        // 当start > end 说明一边的子树已经遍历完 且中间未返回false
        if (start > end) return true; // 递归出口
        // 因为是前序遍历 中左右 当前片段起始位置的元素为中间(根)节点
        let root = arr[start];
        // 关键点 因为每次递归 左子树的最大值会缩小
        // 右子树的最小值会增大 所以如果子树还没start > end的情况下
        // 左子树中间节点大于它的右子节点 或 右子树中间节点小于它的左子节点
        // 说明数组不符合二叉查找树
        if (root < min || root > max) return false; // 递归出口
        // 记录右子树起始位置索引
        // 注意 不一定是右子树最小值
        let right_start;
        // 遍历的起始位置 从中间节点后一位开始
        for (right_start = start + 1; right_start <= end; right_start++) {
            // 找到 第一个大于 子树中间节点的索引位置
            // 作为右子树起始点
            if (arr[right_start] > root) break;
        }
        // 分别递归左右子树 有一个返回false 整个return结果为false
        // 注意 从这递归时 就将数组断开成左右子树范围 分别去递归遍历
        return 判断(arr, start + 1, right_start - 1, min, root - 1) &&
            判断(arr, right_start, end, root + 1, max);
    }
    // Number.是限制数组内数字在可计算范围
    return 判断(arr, 0, arr.length - 1, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
}

// 验证
const 正确例子 = [8, 5, 1, 7, 10, 12];
const 错误例子 = [8, 5, 10, 1, 7, 12];
console.log(fn(正确例子)); // true  
console.log(fn(错误例子)); // false