/**
* 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 {
public:
bool isValidBST(TreeNode* root) {
if (!root) {
return true;
}
int max = INT_MIN;
int min = INT_MAX;
return travel(root, max, min);
}
bool travel(TreeNode* node, int& max, int& min) {
max = node->val > max ? node->val : max;
min = node->val < min ? node->val : min;
int tmpmax, tmpmin;
if (node->left) {
tmpmax = INT_MIN;
tmpmin = INT_MAX;
if (!travel(node->left, tmpmax, tmpmin)) {
return false;
} else if (tmpmax >= node->val) {
return false;
}
max = tmpmax > max ? tmpmax : max;
min = tmpmin < min ? tmpmin : min;
}
if (node->right) {
tmpmax = INT_MIN;
tmpmin = INT_MAX;
if (!travel(node->right, tmpmax, tmpmin)) {
return false;
} else if (tmpmin <= node->val) {
return false;
}
max = tmpmax > max ? tmpmax : max;
min = tmpmin < min ? tmpmin : min;
}
return true;
}
};