给定一组数据，检查它是否是二叉搜索树？

Question

该问题的详细描述如下：每行包含两个值 x 和 y，表示具有键 x 的节点是具有键 y 的节点的 parent。第一个y是x的左边child，第二个y是x的右边child。如果 y 是 -1，则没有 x 对应的 child。请注意，树中所有节点的键是 distinct 和 positive.

已添加：我已经在我的代码中发现了一些错误：1.数据集中给出的节点可能不是从第一层到最底层，也就是说读完一行后，我需要搜索parent节点的索引，然后添加child。 2。 isBST() 函数不正确，因为如果 左子树 递归小于当前节点并且 右子树 递归大于当前节点。 第一个很容易解决，但我不知道如何解决第二个

示例输入

第一行的数字表示下面的行数。对于每一行，左边的数字表示 parent，右边的数字表示 child。如果正确的数字是-1，则表示没有对应的child.

示例输出

YES 2

我认为我的代码可以成功通过测试点，而答案应该是“否”。但是，对于那些应该是“YES + num”的情况，我的代码失败了。谁能指出我代码中的错误？

其实我对二叉搜索树的准确定义不是很清楚。对于样本输入，我不认为它是一个完整的二叉树。我需要考虑这棵树的层数吗？

我的想法很简单，我只是读取数据并将它们存储到一个数组中，然后使用属性左边的 child 存储在索引 i 处的值是2 * i 右边的 child 是 2 * i + 1.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BST {

    public static int[] readData() throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // get the number of rows
        int n = Integer.parseInt(br.readLine());
        String[] strs;
        int[] res = new int[2 * n];
        for (int i = 1; i < n + 1; i++) {
            strs = br.readLine().trim().split(" ");
            //System.out.println(Arrays.toString(strs));
            
            // read the left and right number of one row resp.
            int parent = Integer.parseInt(strs[0]);
            int child = Integer.parseInt(strs[1]);
            // which means that there is no corresponding child, use 0 to denote null
            if (child == -1) {
                child = 0;
            }
            // read the second line with the same parent
            if (res[i - 1] == parent) {
            // put the child as the right child 
                res[2 * (i - 1) + 1] = child;
            }
            else {
                res[i] = parent;
                res[2 * i] = child;
            }
        }
        br.close();
        return res;
    }
    
    public static boolean isLeaf(int[] data, int index) {
        
        // if the node is null, it is not a leaf
        if (data[index] == 0) return false;
        
        
        if (2 * index < data.length - 1) {
            // the left and right children are both null
            if (data[2 * index] == 0 && data[2 * index + 1] == 0) {
                return true;
            }
            // the left and right children are not both null
            else {
                return false;
            }
        }
        // 2 * index is out of bound
        else {
            return true;
        }
    }
    
    public static int countLeaf(int[] data) {
        int count = 0;
        for (int i = 1; i < data.length; i++) {
            // if the node is a leaf, count it
            if (isLeaf(data, i)) count++;
        }
        return count;
    }
    
    public static boolean checkBSTprop(int[] data, int index) {
        // no child can be found
        if (2 * index >= data.length) {
            return true;
        }
        // no child
        if (data[2 * index] == 0 && data[2 * index + 1] == 0) {
            return true;
        }
        // left child is 0, right child is nonzero
        if (data[2 * index] == 0 && data[2 * index + 1] > data[index]) {
            return true;
        }
        // right child is 0, left child is nonzero
        if (data[2 * index + 1] == 0 && data[2 * index] < data[index]) {
            return true;
        }
        // both children are nonzero
        if (data[2 * index] < data[index] && data[2 * index + 1] > data[index]) {
            return true;
        }
        // none of the conditions are satisfied
        return false;
    }
    
    public static boolean isBST(int[] data) {
        for (int i = 1; i < data.length; i++) {
            if (!checkBSTprop(data, i)) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) throws IOException {
        int[] res = readData();
        int num = countLeaf(res);
        
        /*
        System.out.println(Arrays.toString(res));
        System.out.println(countLeaf(res));
        System.out.println(checkBSTprop(res, 1));
        System.out.println(checkBSTprop(res, 2));
        System.out.println(checkBSTprop(res, 3));
        System.out.println(checkBSTprop(res, 6));
        System.out.println(isBST(res));
        */
        
        if (isBST(res)) {
            System.out.println("YES " + num);
        }
        else {
            System.out.println("NO");
        }
        
    }
}

Answer 1

您的方法不会始终有效，因为：

二叉搜索树不一定是完整的树
不保证输入的顺序一定是breadth-first
似乎不能保证相同 parent 的两个 children 在输入中紧接着出现。

因此，您不能使用 i 来定义数组中存储节点值的位置，使用类似 2 * (i - 1) + 1 的公式，也不能检查 parent 是否已经存在之前出现过 res[i - 1].

例如，您的程序将对此有效的 BST 回答“否”：

如果我们输入同一棵树，没有不必要的 1 -1（两次），就像这样：

...然后出现out-of-bounds异常。

其次，在isBST中将child的值与其parent的值进行比较是不够的。即使比较没问题，你仍然可能有一个无效的 BST，例如这个：

这是无效的，因为该叶的唯一有效（不同）整数值是 2 或 3。因此您需要检查递归树的筛选范围。

一个实用的解决方案是真正用 Node class 个实例构建树，并让 isBST 成为那个 class 的实例方法，这考虑到了也是这个范围要求。

给定一组数据，检查它是否是二叉搜索树？

Given a set of data, check if it is a Binary Search Tree?

java

binary-search-tree