Предзаказ на строительство BST

Я пытаюсь создать BST из массива обхода предварительного заказа. Я написал следующий код, но не могу понять, где я делаю ошибку. Следующий код возвращает узлы со значениями null. Я использую следующий подход:

10 8 4 5 14 12
Я разделю его (после удаления начального элемента): 8 4 5 и 14 12 (рекурсивно).

public Node generateTree(int ar[], int low, int high) {
    if (ar.length == 0 || low > high)
        return null;

    if (low == high)
        return new Node(ar[low]);

    int partitionPoint  = findPartitionPoint(ar, low, high);

    Node root = new Node(ar[low]);

    if (partitionPoint != -1) {
        root.left = generateTree(ar, low + 1, partitionPoint);
        root.right = generateTree(ar, partitionPoint + 1, high);
    } else {
        root.left = generateTree(ar, low + 1, high);
    }
    return root;
}
private int findPartitionPoint(int ar[], int low, int high) {
    if (high >= ar.length)
        return -1;
    for (int x = low; x <= high; x++) {
        if (ar[x] > ar[low])
            return x-1;
    }

    return -1;
}

person Yo Yo Money Singh    schedule 04.02.2016    source источник


Ответы (1)


Я вычислил виновника. Проблема была с функцией Traversal, которую я написал отдельно. Функция Node здесь принимает значение int, однако в функции Traversal я печатал ее значение String (мой класс Node имеет как String, так и Integer в качестве ключей). Какая глупая ошибка!

Код кажется правильным.

person Yo Yo Money Singh    schedule 04.02.2016