验证二叉搜索树

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

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

我不是故意修复的。您将了解更多信息。