↓Aller au contenu
  1. Tags/

#Trees

15 articles avec ce tag.

Algorithmes & Structures de données Balanced Binary Tree Un arbre est « équilibré en hauteur » si, pour CHAQUE nœud, les hauteurs de ses deux sous-arbres diffèrent d'au plus 1. Vérifie cette propriété. Facile · 2 min Algorithmes & Structures de données Binary Tree Level Order Traversal Renvoie les valeurs d'un arbre binaire niveau par niveau, de haut en bas, chaque niveau dans sa propre liste. Ex : [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]. Moyen · 2 min Algorithmes & Structures de données Binary Tree Maximum Path Sum Trouve la somme maximale d'un CHEMIN dans un arbre binaire (suite de nœuds connectés, chaque nœud au plus une fois, pas besoin de passer par la racine, valeurs possiblement négatives). Difficile · 2 min Algorithmes & Structures de données Construct Binary Tree from Preorder and Inorder Reconstruis l'arbre binaire unique à partir de ses parcours preorder et inorder (valeurs distinctes). Ex : preorder=[3,9,20,15,7], inorder=[9,3,15,20,7]. Moyen · 2 min Algorithmes & Structures de données Diameter of Binary Tree Le diamètre d'un arbre est la longueur (en ARÊTES) du plus long chemin entre deux nœuds quelconques — ce chemin ne passe pas forcément par la racine. Facile · 2 min Algorithmes & Structures de données Implement Trie (Prefix Tree) Implémente un Trie (arbre de préfixes) : insert(word), search(word) (mot complet présent ?) et startsWith(prefix) (un mot commence-t-il ainsi ?). Moyen · 2 min Algorithmes & Structures de données Invert Binary Tree Inverse un arbre binaire en miroir : pour chaque nœud, son sous-arbre gauche devient son sous-arbre droit et vice-versa. Renvoie la racine. (Le fameux problème qui a recalé le créateur de Homebrew chez Google.) Facile · 2 min Algorithmes & Structures de données Kth Smallest Element in a BST Renvoie le K-ième plus petit élément d'un arbre binaire de recherche (K commence à 1). Moyen · 2 min Algorithmes & Structures de données Lowest Common Ancestor of a BST Dans un arbre binaire de RECHERCHE (BST), trouve le plus petit ancêtre commun (LCA) de deux nœuds p et q : le nœud le plus profond qui a p et q dans sa descendance (un nœud est son propre ancêtre). Facile · 2 min Algorithmes & Structures de données Maximum Depth of Binary Tree Renvoie la profondeur maximale d'un arbre binaire : le nombre de nœuds sur le plus long chemin de la racine jusqu'à une feuille. Un arbre vide a une profondeur de 0. Facile · 2 min Algorithmes & Structures de données Same Tree Deux arbres binaires sont-ils identiques : même structure ET mêmes valeurs à chaque position ? Facile · 2 min Algorithmes & Structures de données Serialize and Deserialize Binary Tree Conçois serialize(root) qui transforme un arbre binaire en chaîne, et deserialize(data) qui reconstruit l'arbre EXACT depuis cette chaîne. Le format est libre : seul l'aller-retour compte. Difficile · 2 min Algorithmes & Structures de données Subtree of Another Tree L'arbre subRoot apparaît-il quelque part comme sous-arbre COMPLET de l'arbre root (même structure, mêmes valeurs, jusqu'aux feuilles) ? Facile · 2 min Algorithmes & Structures de données Symmetric Tree Un arbre binaire est-il symétrique, c'est-à-dire son propre miroir autour de son axe central ? Facile · 2 min Algorithmes & Structures de données Validate Binary Search Tree Vérifie qu'un arbre binaire est un BST valide : pour CHAQUE nœud, tout son sous-arbre gauche est strictement inférieur, tout son sous-arbre droit strictement supérieur. Moyen · 2 min