De haut en bas ou en haut?

Question

Je suis confus avec ce problème de Leetscode.com, cet algorithme est-il un Top-down ou Buttom-up?

public static TreeNode addToTree(int arr[], int start, int end){ 
    if (end < start) { 
    return null; 
    } 
int mid = (start + end)/2; 
TreeNode n = new TreeNode(arr[mid]); 
n.left = addToTree(arr, start, mid - 1); 
n.right = addToTree(arr, mid + 1, end); 
return n; 
} 

Merci

Answer 1

C'est une approche descendante. Cet algorithme place l'élément central dans un noeud, puis il construit les sous-arbres gauche et droit. Ainsi, le nœud supérieur est créé en premier, puis l'arborescence se développe vers le bas. Dans une approche ascendante, les sous-arbres gauche et droit seraient créés en premier, puis ils seraient ajoutés à leur parent. Ce serait quelque chose comme ceci:

public static TreeNode addToTree(int arr[], int start, int end){ 
    if (end < start) { 
     return null; 
    } 

    int mid = (start + end)/2; 
    TreeNode left = addToTree(arr, start, mid - 1); 
    TreeNode right = addToTree(arr, mid + 1, end); 
    TreeNode n = new TreeNode(arr[mid]); 
    n.left = left; 
    n.right = right; 
    return n; 
} 

Dans cette approche, les nœuds du bas de l'arbre seraient créés d'abord, et l'arbre serait construit vers le haut.