题解 | #判断是不是二叉搜索树#(中序遍历递归，非递归)

1. 递归

class Solution {
public:
    /**
    中序遍历 保存中序遍历的前一个节点值 进行比较
     */
    TreeNode *pre = NULL;
    bool isValidBST(TreeNode* root) {
        bool flag = true;
        if(root==NULL) return true;
        bool left = isValidBST(root->left);
        if(pre && pre->val > root->val)
            flag = false;
        pre = root;
        bool right = isValidBST(root->right);
        return flag && left && right;
    }
};

2.栈

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        int pre = INT_MIN;
        while(!st.empty() || cur!=NULL){  //当栈不为空 或 当前指针不为空
            while(cur){
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            if(pre>cur->val) return false;
            pre = cur->val;
            cur = cur->right;
        }
        return true;
    }
};