判断BST

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树

分析：递归三要素，迭代中序的写法不太一样

#include "_myPrint.cpp"
#include "stack"
#include "queue"
using namespace std;

// 验证二叉搜索树
// 递归和迭代法
class Solution{
public:
    // inorder iter
    bool verifyBST(TreeNode* root){
        if (!root) return true;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        // 为了和while中统一 这里先不加入root到st中
        while (cur || !st.empty()){
            if (cur){
                st.push(cur);
                cur = cur -> left;
            }else{
                cur = st.top();
                st.pop();
                if (pre -> val >= cur -> val && pre) return false;
                pre = cur;
                cur = cur -> right;
            }
        }
        return true;

    }
    // 递归法 inorder 边遍历边比较
    TreeNode* pre = NULL;
    bool verifyBST_(TreeNode* root){
        if (!root) return true;
        left = verifyBST_(root -> left);
        // 当前层需要做的事情
        if (pre && pre -> val >= root -> val) return false;
        pre = root;
        right = verifyBST_(root -> right);
        // 当前层的返回结果 节点的左右子树是否都满足
        return left && right;
    }

};

int main(){
    Solution s;

}