Я пытаюсь создать 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;
}