## [98\. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)

Given the `root` of a binary tree, _determine if it is a valid binary search tree (BST)_.

A **valid BST** is defined as follows:

- The left

subtree

of a node contains only nodes with keys **less than** the node's key.
- The right subtree of a node contains only nodes with keys **greater than** the node's key.
- Both the left and right subtrees must also be binary search trees.

**Example 1:**


**Input:** root = \[2,1,3\]
**Output:** true

**Example 2:**


**Input:** root = \[5,1,4,null,null,3,6\]
**Output:** false
**Explanation:** The root node's value is 5 but its right child's value is 4.

**Constraints:**

- The number of nodes in the tree is in the range `[1, 104]`.
- `-231 <= Node.val <= 231 - 1`

/**
 * 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 isValid(root, nullptr, nullptr);
    }
    bool isValid(TreeNode* root, TreeNode* left, TreeNode* right) {
        if(!root) return true;
        
        // 其中一個條件不符合就 return false
        // 如果左邊 node 存在，且大於等於 root 的值
        // 如果右邊 node 存在，且 root 的值大於等於右邊 node 的值
        if((left && left->val >= root->val) || right && root->val >= right->val)
            return false;
        
        // 走訪左邊的樹，最大值為 root，走訪右邊的樹，最小值為 root
        return isValid(root->left, left, root) && isValid(root->right, root, right);
    }
};

:::success
- 時間複雜度：$O(N)$
- 空間複雜度：$O(N)$
:::