Während des Interviews stieß ich auf eine Frage: Wie finde ich den am weitesten entfernten Blattknoten eines binären Baumes und den Abstand von diesem Blattknoten zum Wurzelknoten?
Die erste Reaktion ist definitiv eine Rekursion
Wie können wir den am weitesten entfernten Blattknoten finden und den Abstand von diesem Blattknoten zum Wurzelknoten aufzeichnen? Verwenden Sie eine Liste, um den Pfad vom Stammknoten zum Blattknoten zu verwalten. Die Länge dieser Liste ist -1, was der Abstand vom Blattknoten zum Wurzelknoten ist. Der letzte Knoten der Liste richtet sich an den Blattknoten.
Ich muss keinen binären Baum entwerfen. Ein weiterer Artikel für bestimmte Codes.
/ *** Finden Sie den am weitesten entfernten Blattknoten*/ public void findFarestleaf () {list <node> path = new ArrayList <node> (); LIST <Knode> longestPath = findlongestPath (root, path); Node leaf = longestPath.get (longestPath.size () - 1); System.out.println ("Der am weitesten entfernte Blattknoten ist <" + leaf.key + "," + leaf } publiclist <node> findlongestPath (Knoten x, list <node> path) {if (x == null) return path; // Jede Rekursion muss erstellt werden, andernfalls werden die rekursiven Zweige auf derselben Liste erfolgen. Tatsächlich werden alle Knoten dieser Liste hinzugefügt. LIST <Snode> curpath = new ArrayList <node> (); curpath.addall (Pfad); curpath.add (x); LIST <Knode> linksPath = findlongestPath (X.Left, Curad); LIST <Knode> rightPath = findlongestPath (X.Right, Curad); if (linke path.size ()> rechterPath.size ()) return linke path; sonst return rightpath zurück; }Der obige Artikel, der nach dem am weitesten entfernten Blattknoten (Beispielerklärung) des binären Baums sucht, ist der gesamte Inhalt, den ich mit Ihnen teile. Ich hoffe, es kann Ihnen eine Referenz geben und ich hoffe, Sie können Wulin.com mehr unterstützen.