# 验证二叉搜索树

go评论59阅读模式

Validate a Binary Search Tree

# 问题

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

``````          2
/ \
1   3

``````

``````          5
/ \
1   4
/ \
3   6

```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 &amp;&amp; !(root.left.val &lt; root.val) || root.right != null &amp;&amp; !(root.right.val &gt; root.val))
return false;

isValidHelper(root.right);

return true;
}
}

``````

# 答案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.

• 本文由 发表于 2020年10月5日 19:57:16
• 转载请务必保留本文链接：https://go.coder-hub.com/64208170.html
• binary-search-tree
• depth-first-search
• java

go 63

go 67

go 66

go 63