98. 驗證二叉搜索樹

中序遍歷

搜索二叉樹當中，左樹數值 < 當前節點數值 < 右樹數值，所以第一個判斷方式，就是中序遍歷，只要數值是遞增的，那就是一個搜索二叉樹。

1. 遞迴

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<int> nums;
        auto dfs = [&](this auto&&dfs, TreeNode* node) -> void {
            if(node->left) dfs(node->left);
            nums.push_back(node->val);
            if(node->right) dfs(node->right);
        };
        dfs(root);
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i - 1] >= nums[i]) return false;
        }
        return true;
    }
};

2. 用棧中序遍歷

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;

        // 中序遍歷 左中右, 穿插比較邏輯
        while(!stk.empty() || cur) {
            if(cur) {
                stk.push(cur);
                cur = cur->left;
            }
            else {
                cur = stk.top(); stk.pop();
                if(prev && prev->val >= cur->val) {
                    return false;
                }
                prev = cur;
                cur = cur->right;
            }
        }
        return true;
    }
};

方法二

第二種方式：對於每個點，都應該要滿足以下條件\

• 左樹是一個搜索二叉樹
• 右樹是一個搜索二叉樹
• 左樹最大值 < 當前數值 < 右樹最小值。
  假如遇到空節點，就將最大與最小值設定成極小與極大數值，避免影響判斷結果。剩下的在註解裡面有寫到。

全局變數法

class Solution {
private:
    long long mn, mx;
public:
    bool isValidBST(TreeNode* root) {
        auto check = [&](this auto&&check, TreeNode* node) -> bool {
            if(!node) {
                mn = LLONG_MAX;
                mx = LLONG_MIN;
                return true;
            }
            
            if(!check(node->left)) return false; // check 會更改全域變數 mn, mx
            long long leftMin = mn, leftMax = mx; // 此時 mn, mx 是左樹的最大最小值
            
            if(!check(node->right)) return false;
            long long rightMin = mn, rightMax = mx; // 此時 mn, mx 是右樹的最大最小值
            
            mn = min(min(leftMin, rightMin), (long long)node->val);
            mx = max(max(leftMax, rightMax), (long long)node->val); // 更新這棵子樹的最大最小值
            
            return leftMax < node->val && node->val < rightMin;
        };
        return check(root);     
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$