98. Validate Binary Search Tree

🟠   🔖  树 深度优先搜索 二叉搜索树 二叉树  🔗 LeetCode

题目

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3]

Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]

Output: false

Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -2^31 <= Node.val <= 2^31 - 1

题目大意

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：

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

解题思路

初学者做这题很容易有误区：BST 不是左小右大么，那我只要检查 root.val > root.left.val 且 root.val < root.right.val 不就行了？

这样是不对的，因为 BST 左小右大的特性是指 root.val 要比左子树的所有节点都更大，要比右子树的所有节点都小，只检查左右两个子节点是不够的。

正确解法是通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，递归地检查每个节点的值，将当前节点值的范围（min 和 max）传递给其左右子树，确保它们也在合适的范围内。

代码

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  const helper = (root, min, max) => {
    if (!root) return true;
    if (min != null && root.val <= min) return false;
    if (max != null && root.val >= max) return false;
    return (
      helper(root.left, min, root.val) && helper(root.right, root.val, max)
    );
  };
  return helper(root, null, null);
};

相关题目

相关题目

• 94. 二叉树的中序遍历
• 501. 二叉搜索树中的众数

- [94. 二叉树的中序遍历](./0094.md)
- [501. 二叉搜索树中的众数](https://leetcode.com/problems/find-mode-in-binary-search-tree)