C# LeetCode 104: Maximum Depth of Binary Tree - Easy
Problema Donada l'arrel d'un arbre binari, retorna la seva profunditat màxima. La profunditat màxima és el nombre de nodes al llarg del camí més llarg des de l'arrel fins a la fulla més llunyana.
Enfocament general S'utilitza recursió per explorar tots els camins des de l'arrel fins a les fulles. Cada crida recursiva calcula la profunditat màxima del subarbre actual i la funció combina aquests resultats per obtenir la profunditat global.
Cas base Si el node actual és null hem passat una fulla i la profunditat és 0. Exemple de condició en codi: if (root == null) return 0;
Pas recursiu Per a qualsevol node no nul, la profunditat màxima és 1 pel propi node més el major entre les profunditats màximes del subarbre esquerre i dret. En codi: return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
Explicació amb exemple Considera un arbre simple amb arrel 1, fills 2 i 3, i 2 amb fills 4 i 5. Calculem recursivament: MaxDepth(1) = 1 + max(MaxDepth(2), MaxDepth(3)). MaxDepth(2) = 1 + max(MaxDepth(4), MaxDepth(5)). MaxDepth(4) i MaxDepth(5) retornen 1 perquè els seus fills són null. Així MaxDepth(2) = 2, MaxDepth(3) = 1 i finalment MaxDepth(1) = 3.
Com funciona la pila de crides Cada crida recursiva s'apila fins a arribar a null. En tornar de la crida se suma 1 per cada node per reflectir la inclusió d'aquest node en la profunditat. La pila garanteix que es completa un subarbre abans de combinar resultats i tornar al nivell superior.
Per què els números augmenten En desfer la pila de crides s'afegeix 1 en cada retorn per comptar el node actual, per això la profunditat s'acumula des de les fulles cap a l'arrel.
Exemple d'implementació en C# public int MaxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right)); }
Complexitat Temps O(n) perquè es visita cada node una vegada. Espai O(h) per la profunditat de la pila de recursió on h és l'altura de l'arbre; en el pitjor cas h = n per a un arbre degenerat.
Aplicació pràctica i beneficis Aquest patró recursiu és útil en molts problemes d'arbres com la cerca d'altures, verificació d'equilibri, i càlcul de rutes. Entendre la crida recursiva i la gestió de la pila ajuda a dissenyar solucions eficients i correctes.
Sobre Q2BSTUDIO Q2BSTUDIO és una empresa de desenvolupament de programari i aplicacions a mida especialitzada en solucions tecnològiques avançades. Oferim programari a mida, aplicacions a mida i serveis integrals en intel·ligència artificial, incloent IA per a empreses, agents IA i solucions personalitzades d'automatització. A més, proporcionem serveis de ciberseguretat per protegir els teus sistemes i dades, serveis cloud AWS i Azure per desplegar i escalar aplicacions, i serveis d'intel·ligència de negoci amb Power BI per convertir dades en decisions accionables. El nostre equip combina experiència en desenvolupament, intel·ligència artificial i ciberseguretat per lliurar projectes robustos i orientats a resultats.
Paraules clau aplicacions a mida, programari a mida, intel·ligència artificial, ciberseguretat, serveis cloud AWS i Azure, serveis d'intel·ligència de negoci, IA per a empreses, agents IA, Power BI.
Contacte Si busques implementar algorismes eficients, desenvolupar aplicacions a mida, integrar intel·ligència artificial o millorar la seguretat i governança al núvol, Q2BSTUDIO pot ajudar-te a dissenyar i desplegar la solució adequada per al teu negoci.
