Au cours de l'entretien, j'ai rencontré une question: comment trouver le nœud feuille le plus éloigné d'un arbre binaire et la distance de ce nœud feuille au nœud racine?
La première réaction est définitivement la récursivité
Comment trouver le nœud feuille le plus éloigné et également enregistrer la distance de ce nœud feuille au nœud racine? Utilisez une liste pour maintenir le chemin du nœud racine au nœud feuille. La longueur de cette liste est -1, qui est la distance du nœud feuille au nœud racine. Le dernier nœud de la liste est au nœud feuille.
Je n'ai pas besoin de concevoir un arbre binaire. Voir un autre article pour des codes spécifiques.
/ ** * trouver le nœud de feuille le plus éloigné * / public void findfarestleaf () {list <node> path = new ArrayList <Node> (); List <Node> longestpath = findLongestPath (root, chemin); Node Leaf = longestpath.get (longestpath.size () - 1); System.out.println ("Le nœud de feuille le plus éloigné est <" + leaf.key + "," + leaf.value + ">, et la distance au nœud racine est:" + (longestpath.size () - 1)); } public List <Node> findLongestPath (nœud x, list <Node> path) {if (x == null) return path; // Chaque récursivité doit être créée, sinon les branches récursives seront effectuées sur la même liste. En fait, tous les nœuds sont ajoutés à cette liste. List <Node> currPath = new ArrayList <Node> (); currPath.addall (path); currPath.add (x); List <Node> LeftPath = FindLongestPath (x.left, currPath); Liste <Node> RightPath = FindLongestPath (X.Right, CurrPath); if (LeftPath.size ()> RightPath.size ()) return LeftPath; sinon retourner le chemin de droite; }L'article ci-dessus à la recherche du nœud de feuille le plus éloigné (exemple explication) de l'arbre binaire est tout le contenu que je partage avec vous. J'espère que cela pourra vous donner une référence et j'espère que vous pourrez soutenir Wulin.com plus.