验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

// 思路一：如果是二叉搜索树，那么进行一次中序遍历，得到的应该是一个升序的结果
function juegeBFT(root) {
    let result = [];
    result = inOrder(root);
    let i = 0;
    while (i < result.length - 1) {
        if (result[i + 1] > result[i]) {
            i++
        } else {
            return false;
        }
    }
    return true;
    
    // 中序遍历工具函数
    function inOrder(node) {
        if (node) {
            return [...inOrder(node.left), node, ...inOrder(node.right)]
        }
    }
}

// 更优的代码
// 其实我们在中序遍历的时候，不需要将结果保存成数组，而只需要在遍历过程中和他的前继节点比较，大于其前继节点即可
function isBFT(root) {
    root.pre = null;
    return helper(root);
    // 工具函数
    function helper(node) {
        if (node === null) {
            return true
        }
        if (!helper(node.left)) {
            return false
        }
        if (node.pre && node.pre.val >= node.val) {
            return false
        }
        node.pre = node;
        return helper(node.right);
    }
}