98. Validate Binary Search Tree
給定一個二元樹的根節點，判斷它是否是一個有效的二元搜索樹（BST）。
有效的二元搜索樹定義如下：節點的左子樹只包含鍵值小於該節點鍵值的節點。
節點的右子樹只包含鍵值大於該節點鍵值的節點。
左右子樹也必須分別是二元搜索樹。
範例：
輸入：root = [2,1,3] 輸出：true
這表明，這個二元樹是一個有效的二元搜索樹，因為根節點是 2，其左子節點是 1，右子節點是 3，符合二元搜索樹的所有規則。
Python
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def validate(node, low, high):
# An empty node is considered valid
if not node:
return True
# Check if the current node's value falls within the valid range
if not (low < node.val < high):
return False
# Recursively validate the left subtree and right subtree
# Left subtree must have all values less than the current node's value
# Right subtree must have all values greater than the current node's value
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
# Initialize the recursion with the full range of valid values
return validate(root, float('-inf'), float('inf'))
18.27MB, 39ms
C++
class Solution {
public:
bool isValidBST(TreeNode* root) {
return validate(root, LONG_MIN, LONG_MAX);
}
private:
// Helper function to recursively validate the tree
bool validate(TreeNode* node, long low, long high) {
// Base case: an empty node is a valid BST
if (!node) return true;
// If current node's value is out of the allowed range
if (node->val <= low || node->val >= high) {
return false;
}
// Recursively check the subtrees with updated ranges
// Left subtree must have values less than the current node's value
// Right subtree must have values greater than the current node's value
return validate(node->left, low, node->val) && validate(node->right, node->val, high);
}
};
20.05MB, 7ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root) {
function validate(node, lower, upper) {
// If we reach a null node, return true because null is a valid BST
if (node === null) {
return true;
}
// Check if the current node's value is within the valid range
if (node.val <= lower || node.val >= upper) {
return false;
}
// Recursively validate the left subtree and right subtree
// Left subtree must have all values less than the current node's value
// Right subtree must have all values greater than the current node's value
return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);
}
// Initialize the validation with the widest possible range
return validate(root, -Infinity, Infinity);
};
53.35MB, 50ms
