验证二叉搜索树

[Cosen95]

leetcode: https://leetcode-cn.com/problems/validate-binary-search-tree/

[Cosen95]

分析题目，不难得出：二叉搜索树得到的一定是一个升序的。

所以第一种做法就是先对其进行中序遍历，然后判断是否是一个升序序列即可：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const inorderTraversal = root => {
    if (root) {
        return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
    } else {
        return []
    }
};
var isValidBST = function(root) {
    let res = inorderTraversal(root)
    for (let i = 0; i < res.length; i++) {
        if (res[i] >= res[i+1]) return false
    }
    return true
};

单纯看题目中给出的二叉搜索树的特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

我们可以用递归去实现（遇到有重复性的一般都可通过递归来实现）：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const helper = (root, lower, upper) => {
    if (root === null) return true
    if (root.val <= lower || root.val >= upper) return false
    return helper(root.left, lower, root.val) && helper(root.right, root.val, upper)

}
var isValidBST = function(root) {
    return helper(root, -Infinity, Infinity)
};