java - Hackerrank:这是二叉树吗？

问题陈述：https://www.hackerrank.com/challenges/is-binary-search-tree

我的解决方案：

boolean checkBST(Node root) {
    if(root == null || (root.left == null && root.right == null)) {
        return true;
    } else if(root.left != null && root.right == null) {
        return (root.data > root.left.data) && checkBST(root.left);
    } else if(root.right != null && root.left == null) {
        return (root.data < root.right.data) && checkBST(root.right);
    } else {
        return (root.data > root.left.data) && (root.data < root.right.data) && checkBST(root.left) && checkBST(root.right);
    }
}

很少有测试用例得到“错误答案”。
我知道有很多方法可以解决此问题，但是我正在尝试找出上述解决方案中的错误。

注意：我无法针对那些特定的测试用例进行调试，因为代码没有显示出如何使用这些测试用例构建BST。

编辑：工作解决方案：

  boolean bstUtil(Node root, int min, int max) {
            return root == null
                || (root.data > min && root.data < max)
                && bstUtil(root.left, min, root.data)
                && bstUtil(root.right, root.data, max);
   }

   boolean checkBST(Node root) {
        return bstUtil(root, -1, 10001);
   }

最佳答案

考虑以下树：

             3
            / \
           2   5
          / \
         1   6

即使这不是二叉搜索树，您的测试也将返回true（因为根的左子树包含的节点（6）大于根（3））。

仅检查左子树是否是二叉搜索树并且左子树小于根是不够的。您还必须检查左子节点的每个节点是否小于根节点。