# Leetcode [No. 98] Validate Binary Search Tree (MEDIUM) 解題心得

## 題目

https://leetcode.com/problems/validate-binary-search-tree/description/

## 思路

[參考資料](https://hackmd.io/@Ji0m0/B1dUOaRjN/https%3A%2F%2Fhackmd.io%2F%40Ji0m0%2FBkgKmiIdO)

+ 這個解法主要是透過inorderTraversal的性質來解題
+ 一個BST再經過inorderTraversal後，會是monotonic increasing的
+ 所以先把它存起後再去做比較～

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        // implement a inorder traversal first
        vector<int> res;
        inorderTraversal(root, res);
        for(int i = 1 ; i < res.size(); i++)
        {
            if(res[i] > res[i-1])
            {
                continue;
            }
            else 
            {
                return false;
            }
        }
        return true;
    }
    void inorderTraversal(TreeNode* node, vector<int>& res)
    {
        if(node->left) inorderTraversal(node->left, res);
        res.emplace_back(node->val);
        if(node->right) inorderTraversal(node->right, res);
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果

## 改良:

這種tree-based的問題除了iterative approach外，一定也都有recursive的解法。

以BST來說，我們就主要是確保每一個node都符合BST的特性，也就是left < right.

+ 對左邊的node來說，最多不能超過現在的node.
+ 對右邊的node來說，最低不能低於現在的node.

class Solution {
public:
    bool _isValidBST(TreeNode *node, TreeNode *max_node, TreeNode *min_node) {
      if (!node)
        return true;
      if (max_node && node->val >= max_node->val)
        return false;
      if (min_node && node->val <= min_node->val)
        return false;
      return _isValidBST(node->left, node, min_node) &&
             _isValidBST(node->right, max_node, node);
    }
    bool isValidBST(TreeNode* root) {
      return _isValidBST(root, nullptr, nullptr);
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果


---

## 三訪

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, 1001, -1001);
    }
    bool helper(TreeNode* node, int maxVal, int minVal)
    {
        if (!node) return true;
        if (node->val >= maxVal) return false;
        if (node->val <= minVal) return false;
        return helper(node->left, node->val, minVal) && helper(node->right, maxVal, node->val);
    }
};