LeetCode-98-验证二叉搜索树

一：题目描述

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

有效二叉搜索树定义如下：

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

二：示例与提示

示例 1:

1 2	输入：root = [2,1,3] 输出：true

示例 2:

1
2
3

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示:

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

三：思路

`二叉搜索树特性 + 升序数组`

二叉搜索树的特性
- 如果二叉树的左子树不为空，那么其左子树的所有节点的值小于根节点的值
- 如果二叉树的右子树不为空，那么其右子树的所有节点的值要大于根节点的值
利用中序遍历的顺序，左中右的遍历顺序，会将二叉搜索树的节点按照升序排序的顺序输出
我们就只用判断这个数组是否符合升序排序即可

`比较节点之间的值大小`

在遍历的时候就进行比较操作，相邻两个节点值的大小，如果符合二叉搜索树的条件的话返回true，否则返回false

四：代码

`二叉搜索树特性 + 升序数组`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    中序遍历二叉搜索树 将其输出到一个数组中
    判断这个数组是否升序排序
    const res = []
    const getTree = (root, res) => {
        if(!root) return res
        getTree(root.left, res)
        res.push(root.val)
        getTree(root.right, res)
        return res
    }
    const result = getTree(root, res)
    for(let i = 0; i < result.length; i++){
        if(result[i] >= result[i+1]){
            return false
        }
    }
    return true
};

`比较节点之间的值大小`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    let pre = null
    const getTree = (root) => {
        if(!root) return true
        //左中右
        let left = getTree(root.left)
        //中
        //如果当前节点元素值大于最小值 更新最小值 保证升序
        if (pre !== null && pre.val >= root.val)
            return false;
        pre = root;
        //右
        let right = getTree(root.right)
        return left && right       
    }
    return getTree(root)
};