Validate Binary Search Tree.png
解題思路 ：
test case 很賊會使用 INT_MAX 或是 INT_MIN 來測試 所以在 solution 1 的方法中 使用的邊界改成 LLONG_MIN 跟 LLONG_MAX 來避免超過極值的問題 基本就是設定上下邊界遞歸的方式檢查左右子節點 如果真的忘記還可以用最後一招 inorder traversal 一次整棵樹 把數值存入 vector 然後掃過整個 vector 看看是否有後面的值大於等於前面的狀況 有就代表不是 BST
C++ code :
<pre><code>
//solution 1
/**
- Definition of TreeNode:
- class TreeNode {
- public:
int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}- }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
bool helper(TreeNode *root, long long min, long long max) {
if (root == NULL) return true;
if (root->val <= min || root->val >= max) return false;
return helper(root->left, min, root->val) && helper(root->right, root->val, max);
}
bool isValidBST(TreeNode *root) {
if (root == NULL) return true;
return helper(root, LLONG_MIN, LLONG_MAX);
}
};
//solution 2
/**
- Definition of TreeNode:
- class TreeNode {
- public:
int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}- }
*/
void inorder(TreeNode *root, vector<int> &v)
{
if(root != nullptr)
{
inorder(root->left, v);
v.emplace_back(root->val);
inorder(root->right, v);
}
}
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
bool isValidBST(TreeNode *root) {
// write your code here
if(root == nullptr) return true;
vector<int> treeValue;
inorder(root, treeValue);
for(int i = 0; i < treeValue.size() - 1; i++)
{
if(treeValue[i] >= treeValue[i+1]) return false;
}
return true;
}
};
