英文:
Validate a Binary Search Tree
问题
我正在解决一道LeetCode的问题，要求我检查一个二叉搜索树是否有效。到目前为止，我的解决方案只通过了75个测试案例中的58个。对于我哪里出错了以及如何修复它，你有什么指点吗？
以下是问题描述：
给定一个二叉树，判断它是否是一个有效的二叉搜索树（BST）。
假设BST的定义如下：
- 节点的左子树只包含键值小于节点键值的节点。
- 节点的右子树只包含键值大于节点键值的节点。
- 左子树和右子树必须也是二叉搜索树。
示例1：
2
/ \
1 3
输入: [2,1,3]
输出: true
示例2：
5
/ \
1 4
/ \
3 6
输入: [5,1,4,null,null,3,6]
输出: false
解释: 根节点的值是5，但它的右子节点的值是4。
这是我的解决方案：
```java
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;
}
}
英文:
I am working on a leetcode problem where I am asked to check whether or not a Binary Search Tree is valid. So far, my solution only passes 58 out 75 test cases. Any pointers on where I went wrong and how to fix it?
Here is the question:
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Input: [2,1,3]
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Here is my Solution:
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;
}
}
答案1
得分: 1
你的程序在类似这样的情况下失败：
5
3 7
1 6
因为你只比较子树根部的值。
我故意不提供修复方法。你会通过自己找到解决方法而获得更多的学习。
英文:
Your program fails in cases like this:
5
3 7
1 6
because you only compare the value at the root of the subtrees.
I don't give a fix on purpose. You will learn more finding that out yourself.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论