Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
confused
what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.
The serialization of a binary tree follows a level order traversal, where ‘#‘ signifies a path terminator where no node exists below.
Here‘s an example:
1
/ 2 3
/
4
5
The above binary tree is
serialized as "{1,2,3,#,#,4,#,#,5}".|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 |
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class
Solution {public: bool
isValidBST(TreeNode *root) { if(root == NULL)return
1; return
isBST(root->left,-1000000,root->val) && isBST(root->right,root->val,1000000); } bool
isBST(TreeNode *root, int
min ,int
max ) { if(root == NULL)return
1; if(root->val >=max || root->val <= min)return
0; return
isBST(root->left,min,root->val) && isBST(root->right,root->val,max); }}; |
Validate Binary Search Tree,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3606315.html