leetcode 98. 验证二叉搜索树 Validate Binary Search Tree (使用c++/java/python)
https://leetcode-cn.com/problems/validate-binary-search-tree/
https://leetcode.com/problems/validate-binary-search-tree/
利用一个函数判断子树是否在上下限之间,当上下限为null时表示无限大。
每递归一次,父节点就变成左子树的上限、右子树的下限。
执行用时: c++ 8ms; java 1ms; python 84ms
c++
/**
* 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 isValidSubTree(root,NULL,NULL);
}
bool isValidSubTree(TreeNode* root, TreeNode* lowerBound, TreeNode* upperBound)
{
// 判断子树是否在上界和下界之间
if(root==NULL) return true;
if( (lowerBound && lowerBound->val >= root->val) || (upperBound && upperBound->val <= root->val) )
// 下界存在时做判断、上界存在时做判断
return false;
return isValidSubTree(root->left,lowerBound,root)&&isValidSubTree(root->right,root,upperBound);
//父节点作为左子树的上界、右子树的下界
}
};
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidSubBST(root,null,null);
}
public boolean isValidSubBST(TreeNode root, TreeNode lowerB, TreeNode upperB)
{
if(root==null)
return true;
if((lowerB!=null && root.val <= lowerB.val)||(upperB!=null && root.val >= upperB.val))
return false;
return isValidSubBST(root.left,lowerB,root)&&isValidSubBST(root.right,root,upperB);
}
}
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.isValidSubTree(root,None,None)
def isValidSubTree(self, root, lowerB, upperB):
if root is None:
return True
if (lowerB and lowerB.val>=root.val) or (upperB and upperB.val<=root.val):
return False
return self.isValidSubTree(root.left,lowerB,root) and self.isValidSubTree(root.right,root,upperB)