Поиск самого длинного пути в двоичном дереве

Question

Я хочу найти самый длинный путь в двоичном дереве. Я планирую добавить их в список, таким образом, я могу сказать, что мой вражеский персонаж должен пройти длинный путь в удобном режиме.

private static <T> ArrayList<T> depthFirstSearch(BinaryNode<T> node) 
{ 
    if(node != null) 
    { 
     Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>(); 

     stack.push(node); 

     while(!stack.isEmpty()) 
     { 
      BinaryNode<T> currentNode = stack.pop(); 



      if(currentNode.right != null) 
       stack.push(currentNode.right); 

      // We want to visit left child first, so push left node last. 
      if(currentNode.left != null) 
       stack.push(currentNode.left); 
     } 
    } 
} 

Я написал этот код, но это беспорядок. Я пытаюсь использовать DFS, чтобы найти самый длинный путь. Какие-либо предложения?

EDIT: У меня есть высота дерева, я могу получить его, используя это.

public static <T> int height(BinaryNode<T> t) 
{ 
    if (t == null) 
     return -1; 

    else 
     return 1 + Math.max(height(t.left), height(t.right)); 
} 

Мой вопрос: , когда я знаю, что я нашел самый длинный путь с помощью DFS, так что я могу добавить узлы в мой список?

Answer 1

Самый длинный путь в дереве, называется «диаметр». Вы можете увидеть реализацию алгоритма здесь: http://www.geeksforgeeks.org/diameter-of-a-binary-tree/

Answer 2

Проверьте ответ дается Niki в следующей ссылке .. То есть O (п) решение

Diameter of Binary Tree - Better Design