題目：
給定一個二元樹，判斷這個二元樹是否是一個有效的二元搜尋樹（BST, Binary Search Tree）。

一個有效的二元搜尋樹必須滿足以下條件：

1. 節點的左子樹中的所有節點值必須小於當前節點的值。
2. 節點的右子樹中的所有節點值必須大於當前節點的值。
3. 左、右子樹也必須是二元搜尋樹。

範例：
範例 1：

輸入: [2, 1, 3]
    2
   / \
  1   3
輸出: true

範例 2：

輸入: [5, 1, 4, null, null, 3, 6]
    5
   / \
  1   4
     / \
    3   6
輸出: false
解釋: 根節點的值是 5，但是右子節點 4 的左子節點卻有一個值 3 小於 5。

解題思路

這道題的核心在於檢查每個節點是否遵循 BST 的性質，有兩種解法，

一個是利用 left.val < current.val < right.val 的特性的最小最大解法，也就是每個節點值是否在一個合理的範圍內。當遍歷樹時，對於每個節點，我們需要檢查當前節點是否落在的最小值和最大值範圍內。初始情況下，根節點的值可以是無限小到無限大的範圍內。

另一個解法是利用BST中序遍歷的特性會由小到大排列，那麼就可以用這樣特性來檢查該樹是否為BST。

最小最大解法：前序DFS遞迴版本

這邊先實作前序DFS遞迴版本，

實作：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr)
            return true;

        return isBST(root, LONG_MIN, LONG_MAX);
    }

private:
    bool isBST(TreeNode* root, long min, long max) {
        if (root == nullptr)
            return true; // 空樹是有效的 BST

        if (root->val <= min || root->val >= max)
            return false;

        return isBST(root->left, min, root->val) &&
                isBST(root->right, root->val, max);
    }
};

要注意 2147483647 (2^31-1) 的情況，剛好 INT_MAX 就是 2147483647，所以就改用 LONG_MAX，
-2147483648 (INT_MIN) 也比照辦理改成 LONG_MIN，min 與 max 的變數類型也要是 long。

最小最大解法：前序DFS迭代版本

前面用遞迴，這邊改成前序DFS迭代版本，

實作：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) // 空樹是有效的 BST
            return true;

        //TreeNode* curr;
        //long min = LONG_MIN;
        //long max = LONG_MAX;
        stack<tuple<TreeNode*, long, long>> stk;
        //stk.push({root, min, max});
        stk.push({root, LONG_MIN, LONG_MAX});
        while (!stk.empty()) {
            //tie(curr, min, max) = stk.top();
            auto [curr, min, max] = stk.top();
            stk.pop();

            if (curr->val <= min || curr->val >= max)
                return false;

            if (curr->left) {
                stk.push({curr->left, min, curr->val});
            }
            
            if (curr->right) {
                stk.push({curr->right, curr->val, max});
            }
        }
        return true;
    }
};

STL 補充：

• 假如你已經在 while 迴圈外面宣告了 TreeNode* curr 來表示當前的節點，以及最小值 min 和最大值 max，然後想在迴圈內使用這些變數來取出 stack 中的元素，可以利用 std::tie 取出 tuple 中的值。否則就用 auto。
• stk.push(make_tuple(root, LONG_MIN, LONG_MAX)); 跟 stk.push({root, LONG_MIN, LONG_MAX}); 列表初始化寫法是等價的，只是前者 make_tuple 是顯式寫法，後者列表初始化寫法 {} 更簡潔，讓編譯器推斷出你需要的類型。

中序特性解法：中序DFS迭代版本

這邊要善用中序的特性，中序DFS會由小到大進行遍歷，那麼當前節點一定比上次節點還要大，就可以利用這個特性來檢查BST，

實作：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) // 空樹是有效的 BST
            return true;

        TreeNode* prev = nullptr;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) { // 走到左子樹最深處
                stk.push(root);
                root = root->left;
            }

            root = stk.top();
            stk.pop();

            if (prev != nullptr && root->val <= prev->val)
                return false;
            
            prev = root;
            root = root->right;
        }
        return true;
    }
};

中序特性解法：中序DFS遞迴版本

這邊改成中序DFS遞迴版本，

實作：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return inorderDFS(root, prev);
    }
private:
    bool inorderDFS(TreeNode* root, TreeNode*& prev) {
        if (root == nullptr) // 空樹是有效的 BST
            return true;

        // 遞迴檢查左子樹
        if (!inorderDFS(root->left, prev)) return false;

        // 檢查當前節點值是否大於前一個訪問的節點值
        if (prev != nullptr && root->val <= prev->val) {
            return false;
        }
        // 更新 prev 為當前節點
        prev = root;

        // 遞迴檢查右子樹
        if (!inorderDFS(root->right, prev)) return false;

        return true;
    }
};

參考：
#98. Validate Binary Search Tree