Validate Binary Search Tree

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;
}

};