98.验证二叉搜索树

验证二叉搜索树

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

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

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

示例 1：

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

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false

提示：

• 树中节点数目范围在 [1, $10^4$] 内
• $-2^{31}$ <= Node.val <= $2^{31} - 1$

解析

中序遍历 BST 得到的是升序序列，利用这个性质验证。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  let prev = -Infinity;

  function inorder(node) {
    if (!node) return true;
    if (!inorder(node.left)) return false;
    if (node.val <= prev) return false;
    prev = node.val;
    return inorder(node.right);
  }

  return inorder(root);
};

中序遍历过程中检查当前节点是否严格大于前一个节点。时间复杂度 O(n)。