Je fais un effort pour résoudre un problème Profondeur maximale de l'arbre binaire - Leetcode
Le problème est donné comme un exercice sur la récursion de la queue dans un didacticiel LEetCode. Récupération queue - Leetcode P >
Étant donné un arbre binaire, trouvez sa profondeur maximale. P>
La profondeur maximale est le nombre de nœuds le long du chemin le plus long du nœud racine vers le nœud de la feuille la plus éloignée. P>
Remarque: strong> Une feuille est un nœud sans enfants. P>
exemple: strong> p> Effacement d'arbre binaire
[3,9,20, null, null, 15,7] code>, p>class Solution: def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if root is None: return 0 else: left_height = self.maxDepth(root.left) right_height = self.maxDepth(root.right) return max(left_height, right_height) + 1
4 Réponses :
Vous ne pouvez pas. Trivialement, vous pouvez voir qu'il est impossible d'éliminer à la fois tous les appels de queue LHS et les appels de queue RHS. Vous pouvez éliminer un mais pas l'autre. Parlons de cela.
Ouvrons en déclarant franchement que la récursivité est généralement une mauvaise idée em> en python. Il n'est pas optimisé pour des solutions récursives, et même des optimisations triviales (comme l'élimination de l'appel queue) ne sont pas implémentées. Ne faites pas cela ici. P>
Cependant, cela peut être une bonne langue pour illustrer des concepts qui pourraient être plus difficiles à saisir dans d'autres langues (même si celles-ci pourraient être mieux adaptées aux types de solutions que vous êtes Vous recherchez) alors plongez dans. P>
Comme vous semblez comprendre: la récursivité est une fonction s'appelant elle-même. Bien que la logique de chaque fonction puisse changer, ils ont tous deux sections majeures: p>
C'est le cas trivial qui est généralement quelque chose comme Voici où la fonction décide qu'il doit aller plus loin et se recute en soi. p> pour la récursion de la queue, la partie importante est que dans le cas récursif, la fonction ne doit pas nécessairement Faites tout ce qui est em> après avoir recuches. Les langues plus optimisées peuvent déduire cela et jeter immédiatement le cadre de pile contenant le contexte de l'ancien appel dès qu'il recute dans le nouvel appel. Ceci est souvent fait en passant le contexte requis via des paramètres de fonction. P> Imagine une fonction de somme mise en œuvre de cette manière p> Voyez-vous comment j'ai dû Définir une fonction d'aide qui prend des arguments qui ne sont pas naturellement passés par l'utilisateur? Cela peut vous aider avec cela. P> renvoyer 1 code> ou autre cas dégénérés p>
data TreeNode a = TreeNode { val :: a
, left :: Maybe (TreeNode a)
, right :: Maybe (TreeNode a)
}
treeDepth :: TreeNode a -> Int
treeDepth = go 0 0 . Just
where go :: Int -> Int -> (Maybe (TreeNode a)) -> Int
go maxDepth _ Nothing = maxDepth
go maxDepth curDepth (Just node) = let curDepth' = curDepth + 1 :: Int
maxDepth' = max maxDepth curDepth' :: Int
lhsMax = go maxDepth' curDepth' (left node)
in go lhsMax curDepth' (right node)
root = TreeNode 3 (Just (TreeNode 9 Nothing Nothing)) (Just (TreeNode 20 (Just (TreeNode 15 Nothing Nothing)) (Just (TreeNode 7 Nothing Nothing)))) :: TreeNode Int
main :: IO ()
main = print $ treeDepth root
Mon code d'origine avait une faute de frappe dans go qui passait root.left et root.right à la récursion plutôt que nœud.left et nœud.right de sorte qu'il recouvrait infiniment. OMSOPS!
C'est peut-être un peu tard, mais vous pourriez passer une liste de sous-arbres et retirer toujours l'élément racine. Pour chaque récursion, vous pouvez compter la quantité de suppressions.
ici une implémentation dans HASKELL P>
data Tree a
= Leaf a
| Node a (Tree a) (Tree a)
deriving Show
depth :: Tree a -> Integer
depth tree = recursion 0 [tree]
where
recursion :: Integer -> [Tree a] -> Integer
recursion n [] = n
recursion n treeList = recursion (n+1) (concatMap f treeList)
where
f (Leaf _) = []
f (Node _ left right) = [left, right]
root = Node 1 (Node 2 (Leaf 3) (Leaf 3)) (Leaf 7)
main :: IO ()
main = print $ depth root
Chaque algorithme récursif peut être transformé en queue récursive. Parfois, ce n'est tout simplement pas simple et vous devez utiliser une approche légèrement différente.
En cas d'algorithme récursif sur pied pour déterminer la profondeur d'un arbre binaire, vous pouvez traverser l'arbre en cumulant la liste des sous-arbres à visiter ensemble avec les informations de profondeur. Par conséquent, votre liste sera une liste de tuples Voici un aperçu général de la algorithme p> Voici une implémentation SCALAA P> (profondeur: int, nœud: arborescence) code> et votre deuxième accumulateur enregistrera la profondeur maximale. P>
tovisit code> contenant un tuple (1, rootnode) code> et maxdepth code> défini sur 0 li>
ul>
tovisit code> est vide, retourner maxvalue code> li>
ELTENDTREE code>, continuez avec la queue, maxvalue code> reste le même li>
nœud code>, mettre à jour tovisiter code> en ajoutant la sous-arbre à gauche et à droite à sa queue, incrémentation de la profondeur dans le tuple et vérifiez si la profondeur de la profondeur des la tête est plus grande que celle stockée dans maxdepth code> Accumulateur Li>
ol> data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
depthAux :: [(Int, Tree a)] -> Int -> Int
depthAux [] maxDepth = maxDepth
depthAux ((depth, Empty):xs) maxDepth = depthAux xs maxDepth
depthAux ((depth, (Node h l r)):xs) maxDepth =
depthAux (xs ++ [(depth + 1, l), (depth + 1, r)]) (max depth maxDepth)
depth :: Tree a -> Int
depth node = depthAux [(1, node)] 0
Tout programme récursif peut être fait de la pile-coffre-fort strong> J'ai beaucoup écrit sur le sujet de la récursivité et je suis triste lorsque les gens mystagent les faits. Et non, cela fait pas strud> s'appuyer sur des techniques de Daft comme appeler une fonction dans Python ajoute un cadre de pile. Donc, au lieu d'écrire sys.setrecursionlimit () code>. P> f (x) code> pour appeler une fonction, nous écrirons appel (f, x) code>. Maintenant, nous avons le contrôle complet de la stratégie d'évaluation - P> 3
Même après des années, cela ressemble toujours à je dois retourner à ce Q & A. Bon de voir que tu es toujours là.