Во время интервью я столкнулся с вопросом: как найти самый дальний узел листа бинарного дерева и расстояние от этого листового узла до корневого узла?
Первая реакция определенно рекурсия
Как мы можем найти самый дальний узел листа, а также записать расстояние от этого листового узла до корневого узла? Используйте список, чтобы поддерживать путь от корневого узла до листового узла. Длина этого списка составляет -1, который является расстоянием от листового узла до корневого узла. Последний узел списка - это листовой узел.
Мне не нужно разрабатывать двоичное дерево. Смотрите другую статью для конкретных кодов.
/ *** Найти самый дальний узел листа*/ public void findfarestleaf () {list <node> path = new ArrayList <node> (); Список <node> longestpath = findlongestpath (root, path); Узел лист = longestpath.get (longestpath.size () - 1); System.out.println («Самый дальний узел листьев - <» + leaf.key + »,« + leaf.value + »>, а расстояние до корневого узла:» + (longestpath.size () - 1)); } public List <node> findlongestPath (узел x, список <узел> path) {if (x == null) return Path; // Каждая рекурсия должна быть создана, в противном случае рекурсивные ветви будут выполнены в одном и том же списке. На самом деле, все узлы добавляются в этот список. Список <node> currpath = new ArrayList <node> (); curpath.addall (path); curpath.add (x); Список <node> Leathpath = findlongestPath (x.left, curpath); Список <node> rightpath = findlongestpath (x.right, curpath); if (LeathPath.Size ()> rightPath.size ()) return Lewlepath; иначе вернуть rightpath; }Приведенная выше статья в поисках самого дальнего листового узла (пример объяснения) двоичного дерева - это все контент, которым я делюсь с вами. Я надеюсь, что это может дать вам ссылку, и я надеюсь, что вы сможете поддержать Wulin.com больше.