98、验证二叉搜索树

;(function () {
  /**
   * 98. 验证二叉搜索树
   * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
   * 有效 二叉搜索树定义如下：
   *  -- 1. 节点的左子树只包含 小于 当前节点的数。
   *  -- 2. 节点的右子树只包含 大于 当前节点的数。
   *  -- 3. 所有左子树和右子树自身必须也是二叉搜索树。
   *
   * 输入：root = [2,1,3]
   * 输出：true
   *
   * 输入：root = [5,1,4,null,null,3,6]
   * 输出：false
   * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
   *
   * [2,2,2] -- false
   * [1,null,1] -- false
   * [5,4,6,null,null,3,7] -- false
   * [0,null,-1] -- false
   * [32,26,47,19,null,null,56,null,27] -- false
   */

  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 {
    // 方法一：递归（官方提供）
    // const helper = (root: TreeNode | null, lower: number, upper: number): boolean => {
    //     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);
    // }
    // return helper(root, -Infinity, Infinity);

    // 方法二：中序遍历（官方提供）
    let stack = []
    let inorder = -Infinity
    while (stack.length || root !== null) {
      while (root !== null) {
        stack.push(root)
        root = root.left
      }
      root = stack.pop() || null
      // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
      if (root) {
        if (root.val <= inorder) {
          return false
        }
        inorder = root.val
        root = root.right
      }
    }
    return true

    // 方法三：
  }
})()