5/4 LeetCode每日一题 98. 验证二叉搜索树
在？进来看看码
题面：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入: 2 / \ 1 3 输出: true 示例 2:
输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
分析：
BST的基础知识。对于一棵二叉搜索树来说，树上的每一个节点都是一棵BST。不难想到用递归的方法求解。
同时，树的数组表示法就是把一棵树中序遍历。只要保证中序遍历后的数组严格递增就能证明是一棵BST。
注意，这里的样例有一个INT_MAX，具体实现我使用了long
解法1：递归
class Solution {
public:
bool valid(TreeNode* root,long int lower, long int higher){
if (!root) return true;//空节点必然是BST
if (root->val >= higher || root->val <= lower)
return false;//二叉搜索树必然保持左右子树不超过当前的最大值和最小值
return (valid(root->left, lower, root->val)&&
valid(root->right, root->val, higher));
}
bool isValidBST(TreeNode* root) {
return valid(root, LONG_MIN, LONG_MAX);
}
};
解法2：中序遍历数组化
class Solution {
public:
vector<int> v;
void dfs(TreeNode* root)
{
if (!root)
return ;
dfs(root->left);
v.push_back(root->val);
dfs(root->right);
}
bool isValidBST(TreeNode* root) {
if (!root) return true;
dfs(root);
for (int i=0;i<v.size()-1;i++)
{//验证严格递增
if (v[i+1]<=v[i])
return false;
}
return true;
}
};
———— e n d ————