跳至主要內容

98. 验证二叉搜索树


98. 验证二叉搜索树open in new window

🟠   🔖  深度优先搜索 二叉搜索树 二叉树  🔗 力扣open in new window LeetCodeopen in new window

题目

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, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1

题目大意

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

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

解题思路

初学者做这题很容易有误区:BST 不是左小右大么,那我只要检查 root.val > root.left.valroot.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二叉树的中序遍历open in new window[✓] 深度优先搜索 1+
501二叉搜索树中的众数open in new window 深度优先搜索 二叉搜索树 1+