Ошибка Java stackoverflow в рекурсивной функции

Question

Когда я вызываю эту функцию, почему возникает ошибка stackoverflow? Я проверил условия терминала, но не могу понять, где проблема.

public static TreeNode buildTree(int t1, int t2, ListNode[] nodeArray) {  
    if(t1 == t2){ 
     TreeNode temp = new TreeNode(nodeArray[t1].val); 
     temp.left = null; 
     temp.right = null; 
     return temp; 
    } 
    else if(t1 > t2){ 
     return null; 
    } 

    else{ 
     TreeNode root = new TreeNode(nodeArray[(t1+t2)/2].val); 
     root.left = buildTree(0,(t1+t2)/2-1,nodeArray); 
     root.right = buildTree((t1+t2)/2+1,nodeArray.length-1,nodeArray); 
     return root; 
    } 
} 

Answer 1

Похоже, что рекурсивный метод должен работать на диапазоне между t1 и t2, поэтому рекурсивные вызовы должны быть:

root.left = buildTree(t1,(t1+t2)/2-1,nodeArray); 
root.right = buildTree((t1+t2)/2+1,t2,nodeArray); 

Ваши текущие рекурсивные вызовы не сужать диапазон (вы всегда проходят один диапазон от 0 до середины, а другой диапазон от середины до конца nodeArray), поэтому рекурсия никогда не заканчивается.

Answer 2

Это просто Debugging 101.

Поместите следующую строку в качестве первого в методе:

System.out.println("Entry, t1 = " + t1 + ", t2 = " + t2); 

От того, вы будете иметь возможность работать из потока.

Answer 3

Простой пример вызова метода с массивом [0, 1, 2, 3, 4], как buildTree (0, 4, массив):

1 root = 2; 
2 buildTree(0, 1); 
3  root = 0; 
4  buildTree(0, -1); 
5   null; 
6  buildTree(1, 4); 
7   root = 2; 
8   buildTree(0, 1); // endless recursion. see 2nd line call