题解 | #判断是不是二叉搜索树#

方法一：递归

二叉搜索树的中序遍历一定是升序数组，所以可以利用递归遍历二叉树，如果前一个结点一定小于当前的结点，则可以判断二叉树为二叉搜索树；否则判断为非二叉搜索树。

时间复杂度：o(n)。

空间复杂度：o(n)。

class Solution {
  public:
  	//初始化前结点值为最小值
    long pre = INT_MIN;
    bool isValidBST(TreeNode* root) {
        if (root == nullptr)
            return true;
		//遍历左结点
        if (!isValidBST(root->left))
            return false;
	  	//判断前结点与当前结点的大小
        if (root->val <= pre)
            return false;
        pre = root->val;

        if (!isValidBST(root->right))
            return false;

        return true;
    }
};

方法二：栈（非递归）

原理与方法一相同，不同的是使用辅助栈来得到二叉树的中序遍历，对中序遍历进行是否升序的判断。

时间复杂度：o(n)。

空间复杂度：o(n)。辅助栈和辅助数组所需空间为o(n)，因为辅助栈减少一个结点，辅助数组才写入一个结点。

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

        stack<TreeNode*> temp;
        vector<int> in_order;
        //中序遍历
        while (!temp.empty() || root != nullptr) {
            while (root != nullptr) {
                temp.push(root);
                root = root->left;
            }

            TreeNode* node = temp.top();
            temp.pop();
            in_order.push_back(node->val);

            root = node->right;
        }
        //判断是否为升序
        for (int i = 1; i < in_order.size(); i++) {
            if (in_order[i] <= in_order[i - 1])
                return false;
        }
        return true;
    }
};