验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
codeType
输入：root = [2,1,3]
输出：true
示例 2：
codeType
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
- 树中节点数目范围在[1, 104] 内
- -231 <= Node.val <= 231 - 1
解法
ts
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isValidBST(root: TreeNode | null): boolean {
// 按照中序遍历检查是不是每个前驱都小于当前节点即可
let pre: number | null = null
let res = true
const inOrder = (node: TreeNode | null) => {
if(!node || !res) return
inOrder(node.left)
if(pre === null){ // 第一个遍历到的节点没有前驱
pre = node.val
}else{
if(pre >= node.val){
res = false // 如果前驱大于当前节点
}
pre = node.val // 当前节点就是下一个访问节点的前驱
}
inOrder(node.right)
}
inOrder(root)
return res
};