98. Validate Binary Search Tree
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:
![](https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg)
Input: root = [2,1,3]
Output: true
Example 2:
![](https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg)
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. 二叉树的中序遍历](./0094.md)
- [501. 二叉搜索树中的众数](https://leetcode.com/problems/find-mode-in-binary-search-tree)