要保证 (lower,upper) 为开区间。

因为这样才能保证 root 大于左节点且小于右节点。

遍历二叉树时，永远都是取根的值，处理根的值，左右子树是用来判断该如果处理它们的根。

递归解法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool helper(TreeNode *root,long long lower,long long upper){
        if(root==NULL) return true;//root空则返回真，空树满足二叉搜索树条件
        if(root->val<=lower || root->val>=upper) return false; //若root的值碰到下边界或上边界的值就返回假
        return helper(root->left,lower,root-val)&&helper(root->right,root->val,upper);//递归左右子树都为真时返回真
    }
    bool isValidBST(TreeNode* root) {
        return helper(root,LONG_MIN,LONG_MAX);
    }
};

栈解法

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stk;
        long long prev=(long long)INT_MIN-1;//保存上一个值，下边界是比最小值小的数
        while(root!=NULL || !stk.empty()){
            while(root!=NULL){
                stk.push(root);
                root=root->left;
            }
            root=stk.top();
            stk.pop();
            if(root->val<=prev) return false; //检查上一个值和当前值的大小，若比上一个值小返回假
            prev=root->val;//保存当前值作为下次的上个值
            root=root->right;//移动到右节点
        }
        return true;
    }
};