LeetCode 98 Validate Binary Search Tree
概述
https://leetcode.com/problems/validate-binary-search-tree/
递归法
这里要注意的是，左右子树合法不代表其一定合法，root 的值还必须满足大于左子树的最大值，小于右子树的最小值。
另外还要注意题目的输入范围，用 INT_MIN 和 INT_MAX 不行。
class Solution {
public:
bool isValidBST(TreeNode* root) {
return helper(root, LLONG_MIN, LLONG_MAX);
}
bool helper(TreeNode* root, long minV, long maxV) {
if (!root) return true;
if (root->val >= maxV || root->val <= minV) return false;
return helper(root->left, minV, root->val) && helper(root->right, root->val, maxV);
}
};
要是题目不给输入范围怎么办？实际上可以使用 TreeNode 来存，如果为 nullptr 的话就不检查该边界就好。
附上两年前的 Java 解法：
class Solution {
private int last;
private boolean isFirst;
public boolean isValidBST(TreeNode root) {
last = Integer.MIN_VALUE;
isFirst = true;
return helper(root);
}
private boolean helper(TreeNode node){
if(node==null){
return true;
}
if(node.left!=null){
if(!helper(node.left)){
return false;
}
}
if(node.val<=last){
if(isFirst){
isFirst = false;
last = node.val;
}else{
return false;
}
}else{
if(isFirst){
isFirst = false;
}
last = node.val;
}
if(node.right!=null){
if(!helper(node.right)){
return false;
}
}
return true;
}
}