验证二进制搜索树

Question

我正在处理一个leetcode问题，要求我检查二进制搜索树是否有效。到目前为止，我的解决方案只通过了75个测试用例中的58个。有什么关于我哪里出了问题以及如何解决的建议吗？

问题是：

给定一个二进制树，确定它是否是有效的二进制搜索树(BST(。

假设BST定义如下：

节点的左子树只包含键小于节点键的节点。节点的右子树只包含键大于节点键的节点。左子树和右子树也必须是二进制搜索树。

示例1:

2
/ 
1   3

输入：[2,1,3]

输出：真实

示例2:

5
/ 
1   4
/ 
3   6

输入：[5,1,4，null，null，3,6]

输出：错误

说明：根节点的值为5，但其右子节点的值是4。

这是我的解决方案：

class Solution {
public boolean isValidBST(TreeNode root) {

return isValidHelper(root); 
}

public boolean isValidHelper(TreeNode root)
{
if(root == null)
return true; 


isValidHelper(root.left); 

if(root.left != null && !(root.left.val < root.val) || root.right != null && !(root.right.val > root.val))
return false; 

isValidHelper(root.right); 

return true;
}
}

Answer 1

您的程序在以下情况下失败：

5
3   7
1 6

因为您只比较子树根处的值。

我不会故意给出答案。你会发现更多自己发现。