力扣链接：98.验证二叉搜索树

难度：⭐⭐

✏️ 方法一：

解题关键词：二叉搜索树、中序遍历、栈

解题思路：使用中序遍历，然后判断前一个节点小于后续节点，如果符合条件，那么就是一颗二叉搜索树。

var isValidBST = function (root) {
  // 栈
  let stack = [];
  // 前一个节点的值
  let preNodeValue = -Infinity;

  while (stack.length || root !== null) {
    // 当前节点不为空，一直找最左边的节点
    while (root !== null) {
      stack.push(root);
      root = root.left;
    }

    // 处理当前节点
    root = stack.pop();
    // 如果中序遍历得到的节点的值小于等于前一个 preNodeValue，说明不是二叉搜索树
    if (root.val <= preNodeValue) {
      return false;
    }

    // 更新前一个节点的值
    preNodeValue = root.val;
    // 处理右边节点
    root = root.right;
  }

  return true;
};

✏️ 方法二：

解题关键词：二叉搜索树、递归

解题思路：递归验证每个节点的值是否在指定区间内。

// 验证一个节点的值是否在 lower 和 upper 之间
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);
};