【题目】
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
代码语言：javascript复制示例 :
输入:
/
输出: true
示例 :
输入:
/
/
输出: false
解释: 输入为: [,,,null,null,,]。
根节点的值为 ，但是其右子节点值为 。
【思路】
每个节点，都有值大小的限制，在递归时需要判断是否满足条件。
【代码】
python版本
代码语言：javascript复制# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.isValid(root, sys.maxsize, -sys.maxsize)
def isValid(self, root, max0, min0):
if not root:
return True
if root.val >= max0 or root.val <= min0:
return False
return self.isValid(root.left, root.val, min0) and self.isValid(root.right, max0, root.val)
C 版本
代码语言：javascript复制/**
* 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) {
return isValidBST(root, LONG_MAX, LONG_MIN);
}
bool isValidBST(TreeNode* root, long max0, long min0) {
if(!root)
return true;
if(root->val >= max0 || root->val <= min0)
return false;
return isValidBST(root->left, root->val, min0) && isValidBST(root->right, max0, root->val);
}
};
