Konwersja posortowanej tablicy do binarne drzewo poszukiwań

Question

pracuję nad „Convert posortowanej tablicy do binarne drzewo poszukiwań Przy minimalnej wysokości”, który zapytał:

Biorąc pod uwagę sortowane (rosnące) tablica, przekształcić go stworzyć drzewo binarne o minimalnej wysokości.

Nie jestem w stanie ustalić, dlaczego moja rekurencja nie kończy się tak, jak się spodziewałem. Powinien przestać, gdy minie 7, i nie wydrukuje ponownie 7. Znalazłem też podobną odpowiedź, wygląda na to, że użyłem tej samej strategii co moja, ale działa dobrze. (Nie sądzę, aby moje pytanie było duplikatem tych pytań wymienionych powyżej, ale nadal chcę podziękować ci za ich linkowanie.) Dali mi więcej pomysłu na rozwiązanie mojego problemu.)

Mój kod jest poniżej:

public TreeNode sortedArrayToBST(int[] A) { 
    int len = A.length; 
    if(len <= 0){ 
     return null; 
    } 

    TreeNode root = new TreeNode(A[(len - 1)/2]); 
    if(len == 1){ 
     return root; 
    } 
    else{ 
     helper(root, A, 0, len - 1); 
    } 
    return root; 
} 

public void helper(TreeNode root, int[] A, int leftPoint, int rightPoint){ 
    if((rightPoint - leftPoint) <= 0){ 
     return; 
    } 

    int mid = (rightPoint - leftPoint)/2 + leftPoint; 
    int leftChild = (mid - 1 - leftPoint)/2 + leftPoint; 
    int rightChild = (rightPoint - (mid + 1))/2 + mid + 1; 

    TreeNode left = new TreeNode(A[leftChild]); 
    root.left = left; 

    TreeNode right = new TreeNode(A[rightChild]); 
    root.right = right; 

    helper(root.left, A, leftPoint, mid - 1); 
    helper(root.right, A, mid + 1, rightPoint); 
    return; 
} 

Kiedy go uruchomię, mam to.

Moje wejście
[1,2,3,4,5,6,7,8]

moje wyjście
{4,2,6,1,3,5,7,#,#,#,#,#,#,7,8}

Oczekiwany
{4,2,6,1,3,5,7,#,#,#,#,#,#,#,8}

Dlaczego to duplikat 7 po prawej stronie? Ponieważ 7 zostało użyte, powinno zostać wyrzucone.

I znalazłem mój pomysł jest podobny do poniższego odpowiedź:

public TreeNode sortedArrayToBST(int[] A) { 
    // write your code here 
    int len = A.length; 
    if(len <= 0){ 
     return null; 
    } 
    TreeNode root = helper1(A, 0, len - 1); 
    return root; 
} 

public TreeNode helper1(int[] A, int low, int high){ 
    if(low > high){ 
     return null; 
    } 
    int mid = (high + low)/2; 
    TreeNode root = new TreeNode(A[mid]); 
    root.left = helper1(A, low, mid - 1); 
    root.right = helper1(A, mid + 1, high); 
    return root; 
} 

Answer 1

zjedzmy następującą tablicę:

[1,2,3,4,5,6,7] 

Oczekiwany BST:

 4 
    2  6 
    1 3 5 7 

Aby osiągnąć że możemy przejść w następujący sposób:

for (int i = 0; i < logn; i++) { 
    //insert ith level 
} 

Aby było łatwiej, znajdź min n, czyli n > array.length i n = 2^k.

Na Ith poziomie, począwszy od i = 0 mamy:

n/2^(i+1), 3*n/2^(i+1), 5*n/2^(i+1)...

Liczby powyżej są wszystkie indeksy w tablicy.

public TreeNode sortedArrayToBST(int[] A) { 
    int len = A.length; 
    if(len <= 0){ 
     return null; 
    } 

    int n = 1; 
    int i = 0; 
    while (n < len) { 
     n *= 2; 
     i++; 
    } 

    TreeNode root = new TreeNode(A[n/2]); 

    for (int j = 1; j < i; j++) { 
     insert(root, j, n, A); 
    } 
} 

private void insert(TreeNode root, int j, int n, int[] A) { 

    int helper = n/Math.pow(2, j+1); 
    for (int i = 1; i <= Math.pow(2, j); i ++) { 
     root.add(A[i*helper]); 
    } 
} 

Answer 2

To może działać

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

    return helper1(A, 0, A.length - 1); 
} 
public TreeNode helper1(int[] A, int low, int high) { 
    if (low > high) 
     return null; 

    // Binary Search 
    int mid = low + (high - low)/2; 
    TreeNode root = new TreeNode(A[mid]); 

    root.left = helper1(A, low, mid - 1); 
    root.right = helper1(A, mid + 1, high); 

    return root; 
}