判断二叉树是排序二叉树(二叉搜索树)

方法一：判断中序遍历数列是否递增(非递归)

bool isValidBST(TreeNode* root) {
        stack s;
        TreeNode* p=root;
        if(root==NULL) return true;
        long long temp=(long long)INT_MIN - 1;  //初值，表示刚遍历完的数
        while(p){
            s.push(p);
            p=p->left;
        }
        while(!s.empty()){
            TreeNode* p=s.top();
            s.pop();
            if(p->val<= temp){
                return false; //中序遍历不递增，注意是<=
            }
            temp=p->val;
            p=p->right;
            while(p){
                s.push(p);
                p=p->left;
            }
        }
        return true;
    }

方法二：递归判断

错误思想：

（1）根节点值>左孩子值，根节点值<右孩子值

（2）左右子树都是满足这一条件

       反例： 5和3不满足

正确想法：

    遍历左子树时，保留根节点的值，即上界，实现整个左子树的值都小于根节点；遍历右子树时，根节点的值为下界。

bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) return true;
        if (root -> val <= lower || root -> val >= upper) return false;
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }