解法一：栈 + 中序遍历

1、思路

• 对二叉树进行中序遍历，每个节点存入栈中；

• 若当前节点小于等于栈顶节点，表示该二叉树不是二叉搜索树；

• 时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

2、代码

class Solution {
private:
    stack<int> stk;

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

        bool left = isValidBST(root->left);         //记录左子树是否合法

        if (!stk.empty() && stk.top() >= root->val)
        {
            return false;
        }
        else
        {
            stk.push(root->val);
        }


        bool right = isValidBST(root->right);       //记录右子树是否合法

        return left && right;                       //判断当前树是否合法
    }
};

解法二：不使用额外空间

1、思路

• 递归判断root节点的所有左子树都比它小，所有右子树都比它大；

• 时间复杂度为 $O(N)$ ，空间复杂度为 $O(logN)$ 。

2、代码

class Solution {
public:
    bool helper(TreeNode* root, long long min, long long max)
    {
        if (root == nullptr) return true;

        if (root->val <= min || root->val >= max)   //判断是否在合法区间之外
        {
            return false;
        }

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

    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};