LeetCode 98
Validate Binary Search Tree
- Problem Description:
判断给出的二叉树是否是二叉搜索树。
二叉搜索树:要么是空树,要么是具有以下性质的二叉树:若它的左子树不为空,则左子树上所有结点的值均小于它的根节点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。
具体的题目信息:
https://leetcode.com/problems/validate-binary-search-tree/description/
- Reference : https://blog.csdn.net/qq_30490125/article/details/53135274
-
Solution:
(1)方法一:根据定义递归实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == NULL)
return true;
if (root->left && maxNum(root->left)>= root->val)
return false;
if (root->right && minNum(root->right)<= root->val)
return false;
if (!(isValidBST(root->left)&&isValidBST(root->right)))
return false;
return true;
}
int maxNum(TreeNode* p) {
while(p->right) {
p = p->right;
}
return p->val;
}
int minNum(TreeNode* p) {
while(p->left) {
p = p->left;
}
return p->val;
}
};
(2) 方法二:利用中序遍历把所有结点的值存储在vector数组中,判断数组中元素是否递增排列。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
stack<TreeNode*> node;
vector<int> num;
TreeNode* p = root;
while(p || !node.empty()) {
while(p) {
node.push(p);
p = p->left;
}
p = node.top();
num.push_back(p->val);
node.pop();
p = p->right;
}
for (int i = ; i < num.size()-; i++) {
if (num[i]>=num[i+])
return false;
}
return true;
}
};