98 - 验证二叉搜索树

题目链接

验证二叉搜索树

题目

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

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

思路

使用递归判断左子树和右子树是否都满足条件

代码

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  function isValid(root, lower, upper) {
    if (root.val < upper && root.val > lower) {
      if (!root.left && !root.right) {
        return true;
      } else if (!root.left) {
        return isValid(root.right, root.val, upper);
      } else if (!root.right) {
        return isValid(root.left, lower, root.val);
      } else {
        return (
          isValid(root.left, lower, root.val) &&
          isValid(root.right, root.val, upper)
        );
      }
    } else {
      return false;
    }
  }
  return isValid(root, -Infinity, Infinity);
};

复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。