98. Validate Binary Search Tree

題目網址：https://leetcode.cn/problems/validate-binary-search-tree/

題意：給一 BT 的 root, 返回其是否為 BST。

Solution：

想法：利用 DFS, 當前 node 必須判斷是否在目前的上、下界中, 因此要不斷維護當前的上、下界。若 node->val 滿足當前上下界：

• 遞迴遍歷 node->left, 並把 node->val 設為上界
• 遞迴遍歷 node->right, 並把 node->val 設為下界

下圖中雖然 7 > 4, 但它卻位於 5 的左子樹中（此時的 lower = 4, upper = 5）, 故要返回 false

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        // 要用 long 而非 int, 因為若用 int, 當 root = [INT_MAX] 時, 會返回 false
        return dfs(root, LONG_MIN, LONG_MAX);
    }

private:
    bool dfs(TreeNode* node, long lower, long upper){
        if (!node) {
            return true; // 若 tree 為空樹, 也是合法的 BST
        }

        if (node->val <= lower || node->val >= upper) {
            return false;
        }

        // 當前 node 是合法的, 故遞迴判斷左、右子樹是否合法
        return dfs(node->left, lower, node->val) && 
                dfs(node->right, node->val, upper);
    }
};

• time：$O(n)$ ➔ 遍歷整個 BT
• space：$O(n)$ ➔ 遞迴深度不超過 n