Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

 

confused what 

"{1,#,2,3}" means? 

 

分析：二叉搜索树的中序遍历是从小到大排列的。

 

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution{private:  int pre;  vector
       
         vec;public:  Solution():pre(LONG_MIN) {}  bool isValidBST(TreeNode* root)  {    vec.clear();    if(root == NULL) return true;    if(root->left==NULL && root->right==NULL) return true;    isValid(root);        for(int i=1; i
        
         = vec[i])        return false;            return true;  }    void isValid(TreeNode* root)  {    if(root)    {      isValid(root->left);      vec.push_back(root->val);      isValid(root->right);    }  }};
        
       

 

 

方法二：设置上下界

class Solution{public:  bool isValidBST(TreeNode* root)  {    if(root == NULL) return true;    if(root->left==NULL && root->right==NULL) return true;            return isValid(root, LONG_MIN, LONG_MAX);  }    bool isValid(TreeNode* root, int min, int max)  {    if(root==NULL) return true;    if(root->val <= min || root->val >= max) return false;    return isValid(root->left, min, root->val) && isValid(root->right, root->val, max);  }};