## Saturday, January 12, 2013

### [LeetCode] 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? > read more on how binary tree is serialized on OJ.
» Solve this problem

[解题思路]

[Code]

{10,5,15,#,#,6,20}

``````1:    bool isValidBST(TreeNode *root) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      return VerifyBST(root, false, false, 0,0);
5:    }
6:    bool VerifyBST(TreeNode* root, bool left, bool right, int lmax, int rmin)
7:    {
8:      if(root== NULL)
9:        return true;
10:      if(left && root->val >= lmax) return false;
11:      if(right && root->val <=rmin) return false;
12:      bool leftValid = VerifyBST(root->left, true, ````right````, root->val, rmin);
13:      bool rightValid = VerifyBST(root->right, ````left````, true, lmax, root->val);
14:      return leftValid&&rightValid;
15:    }
``````

``````1:       bool isValidBST(TreeNode *root) {
2:            return IsValidBST(root, INT_MIN, INT_MAX);
3:       }
4:       bool IsValidBST(TreeNode* node, int MIN, int MAX)
5:       {
6:            if(node == NULL)
7:                  return true;
8:            if(node->val > MIN
9:                      && node->val < MAX
10:                      && IsValidBST(node->left,MIN,node->val)
11:                      && IsValidBST(node->right,node->val,MAX))
12:                 return true;
13:            else
14:                 return false;
15:       }
``````