Преобразование отсортированного массива в исключение переполнения стека двоичного поиска (Java)

Question

Это программа для преобразования массива, где элементы сортируются в порядке возрастания, до сбалансированного по высоте BST.

Я ввожу пять элементов, передаю их в массив, сортирует массив и использует методы.

Он производит эту ошибку:

Exception in thread "main" java.lang.StackOverflowError 
    at Solution.sortedArrayToBST(Node.java:26) 

Как исправить эту ошибку?

import java.util.*; 

class Node { 
    int val; 
    Node left; 
    Node right; 

    Node(int x) { 
     val = x; 
    } 
} 

class Solution { 

    public Node sortedArrayToBST(int[] num) { 
     if (num.length == 0) 
      return null; 

     return sortedArrayToBST(num, 0, num.length - 1); 
    } 

    public Node sortedArrayToBST(int[] num, int start, int end) { 

     int mid = (start + end)/2; 
     Node root = new Node(num[mid]); 
     root.left = sortedArrayToBST(num, start, mid - 1); 
     root.right = sortedArrayToBST(num, mid + 1, end); 

     return root; 
    } 

    public static void main(String[] args) { 

     Solution sol = new Solution(); 

     Scanner input = new Scanner(System.in); 
     int[] numbers = new int[5]; 

     System.out.println("Please enter numbers"); 
     for (int i = 0; i < numbers.length; i++) { 
      numbers[i] = input.nextInt(); 
     } 

     // sorting 
     for (int j = 0; j<numbers.length; j++) { 
      for (int k = 0; k < numbers.length; k++){ 
       if (numbers[j] < numbers[k]) { 
        int buffer = numbers[j]; 
        numbers[j] = numbers[k]; 
        numbers[k] = buffer; 
       } 
      } 
     } 

     sol.sortedArrayToBST(numbers, 0, 5); 
     sol.sortedArrayToBST(numbers); 
    } 

} 

Answer 1

sortedArrayToBST с массивом вызовов sortedArrayToBST с 3 параметра (который, в свою очередь, вызывает тот же метод с одним параметром), и вы никогда не выйти из него.

Вы отправляете один и тот же массив одного и того же размера снова и снова в sortedArrayToBST с одним параметром. Вместо этого вы должны создать новый массив, разбив его на два (low-mid и mid + 1 to high).

Answer 2

Метод sortedArrayToBST (num, start, end) не имеет условия завершения, поэтому он никогда не заканчивается. получают ошибку StackOverFlow. Вам нужно добавить условие в начало метода: if (start> end) return null. Вы можете проверить это видео Youtube в разделе «Сортировка массива» на BST: Create a balanced binary search tree from a sorted array