将排序后的数组转换为二进制搜索树(Java)堆栈溢出异常 [英] Convert sorted array to Binary Search Tree (Java) stack overflow exception

问题描述

这是一个程序，用于将数组(其中元素按升序排序)转换为高度平衡的BST.

This is a program for converting an array, where elements are sorted in ascending order, to a height balanced BST.

我输入了五个元素，将它们传递给数组，对数组进行排序并使用方法.

I input five element, pass them to an array, sort the array and use methods.

它会产生此错误:

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);
    }

}

推荐答案

sortedArrayToBST(num，start，end)方法没有终止条件，这就是为什么它永远不会结束的原因，因为您遇到了StackOverFlow错误. 您需要在方法的开头添加一个条件: if(start> end)返回null. 您可以在将数组排序为BST"问题上检查此Youtube视频: 根据排序后的数组创建平衡的二进制搜索树

The method sortedArrayToBST(num, start, end) does not have a termination condition that is why it never ends are you are getting StackOverFlow error. You need to add a condition in the start of the method: if(start > end) return null. You can check this Youtube video on Sorted Array to BST problem: Create a balanced binary search tree from a sorted array

这篇关于将排序后的数组转换为二进制搜索树(Java)堆栈溢出异常的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！