ближайший узел листа из заданного узла в двоичном дереве

Question

Найти ближайший узел листа от данного узла в двоичном дереве.

если дерево:

     1 

       2   3 

      4  5 

     6  7 

    9  8 

чем кратчайший листовой узел от 2: 3. Может ли кто-нибудь помочь мне в разработке в Algo для этого. Благодарю.

Я могу найти, является ли узел корневым узлом (простой DFS), но не может использовать устройство для этого случая, когда узел не является предком самого короткого удаленного листового узла.

Дерево представление:

Class TreeNode{ 
    int val; 
    TreeNode left, right; 
} 

Вам дается с узлом, т.е. t1 и корень, т.е. t.

Answer 1

Чтобы найти ближайший узел в невзвешенном графике, вам необходимо выполнить BFS. Смежными узлами данного узла являются все его дочерние узлы и его предшественник (если есть). Вам нужно будет выбрать соответствующее представление дерева, чтобы вы могли найти предшественника данного узла, а также его дочерние узлы.

Также обратите внимание, что для этой проблемы вам придется рассматривать график как ненаправленный.

Answer 2

1) найти лист, ближайший к корню дерева (DFS)

2) найти глубину данного узла, если вы не знаете, это уже (ДФС)

3) найдите ближайший к данному узлу лист среди его потомков (DFS)

Решение является самым коротким среди 1 + 2 и 3. Оно, вероятно, может быть объединено в одну DFS.

Как указано @Eyal, это неправильно.

Вот исправление:

1) Для каждого узла в дереве, найти ближайший лист среди его потомков (DFS).

2) Для каждого узла по пути от корня дерева до данного узла добавьте расстояние от узла до его ближайшего потомка и расстояние до данного узла.

Решение дается наименьшей суммой.

Вы можете реализовать это следующим образом:

• Start из алгоритма DFS, который находит ближайший потомок лист для всех узлов в дереве.

• Измените рекурсивную функцию так, чтобы она знала: а) глубину текущего узла, пусть Dc, b) глубина данного узла, пусть Dg и c) наименьшая глубина, достигнутая с того момента, как данный узел был замечен , пусть Ds, первоначально установленный в -1, d) ближайший узел до сих пор (не обязательно потомок).

• Перед тем, как оставить функцию, если текущий узел является данным узлом, установите Dg = Ds = Dc; else, если Dc < Ds, обновите Ds = Dc и сохраните ближайший узел между ближайшим до сих пор и ближайшим потомком текущего узла, добавив штраф Dc-Dg на расстояние.