验证二叉搜索树

huangapple
go评论101阅读模式
英文:

Validate a Binary Search Tree

问题

我正在解决一道LeetCode的问题，要求我检查一个二叉搜索树是否有效。到目前为止，我的解决方案只通过了75个测试案例中的58个。对于我哪里出错了以及如何修复它，你有什么指点吗？

以下是问题描述：

给定一个二叉树，判断它是否是一个有效的二叉搜索树（BST）。

假设BST的定义如下：

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

示例1：

  1.           2
  2.          / \
  3.         1   3
  5. 输入: [2,1,3]
  6. 输出: true

示例2：

  1.           5
  2.          / \
  3.         1   4
  4.            / \
  5.           3   6
  7. 输入: [5,1,4,null,null,3,6]
  8. 输出: false
  9. 解释: 根节点的值是5，但它的右子节点的值是4。
  11. 这是我的解决方案：
  13. ```java
  14. class Solution {
  15.     public boolean isValidBST(TreeNode root) {
  16.         
  17.         return isValidHelper(root); 
  18.     }
  19.     
  20.     public boolean isValidHelper(TreeNode root) {
  21.         if (root == null)
  22.             return true; 
  23.         
  24.         isValidHelper(root.left); 
  25.         
  26.         if (root.left != null && !(root.left.val < root.val) || root.right != null && !(root.right.val > root.val))
  27.             return false; 
  28.         
  29.         isValidHelper(root.right); 
  30.         
  31.         return true;
  32.     }
  33. }
英文:

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:

  1.                      2
  2.                     / \
  3.                    1   3

Input: [2,1,3]

Output: true

Example 2:

  1.                      5
  2.                     / \
  3.                    1   4
  4.                       / \
  5.                      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:

  2. class Solution {
  3.     public boolean isValidBST(TreeNode root) {
  4.         
  5.         return isValidHelper(root); 
  6.     }
  7.     
  8.     public boolean isValidHelper(TreeNode root)
  9.     {
  10.         if(root == null)
  11.             return true; 
  12.         
  13.         
  14.         isValidHelper(root.left); 
  15.         
  16.  if(root.left != null &amp;&amp; !(root.left.val &lt; root.val) || root.right != null &amp;&amp; !(root.right.val &gt; root.val))
  17.             return false; 
  18.         
  19.         isValidHelper(root.right); 
  20.         
  21.         return true;
  22.     }
  23. }

答案1

得分: 1

你的程序在类似这样的情况下失败：

  1.      5
  2.    3   7
  3.   1 6

因为你只比较子树根部的值。

我故意不提供修复方法。你会通过自己找到解决方法而获得更多的学习。

英文:

Your program fails in cases like this:

  1.      5
  2.    3   7
  3.   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.

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

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定