¿Cómo encontrar el camino más profundo desde la raíz compuesto por solo 1 en un árbol de búsqueda binario?

Question

Tenemos un árbol binario (no BST) compuesto por solo 0 y 1. tenemos que encontrar el más profundo 1 con un camino desde la raíz formada únicamente por de 1

Fuente: Amazon entrevista Q

Answer 1

public static int findMaxOnesDepth(Node root){ 

     if(root != null && root.getValue() == 1){ 
       return Math.max(1 + findMaxOnesDepth(root.getLeft()), 
          1 + findMaxOnesDepth(root.getRight()); 
     } 
     else { 
      return 0; 
     } 
} 

Si el nodo que está es un '0', entonces la profundidad de ' 1 es 0. De lo contrario, si el nodo en el que se encuentra es un '1', agregue 1 al máximo 'la profundidad de uno' de sus hijos izquierdo y derecho, y devuelva el máximo de esos.

El código anterior se encuentra la longitud, para encontrar los nodos reales a lo largo del camino, se puede usar una lista para realizar un seguimiento de este

public static ArrayList<Node> findLongestOnesPath(Node root){ 

     ArrayList<Node> currStack = new ArrayList<Node>(); 

     if(root != null && root.getValue() == 1){ 

      currStack.add(root); 

      ArrayList<Node> leftStack = findLongestOnesPath(root.getLeft()); 
      ArrayList<Node> rightStack = findLongestOnesPath(root.getRight()); 

      if(leftStack.size() > rightStack.size()){ 
       currStack.addAll(leftStack); 
      } 
      else{ 
       currStack.addAll(rightStack); 
      } 

     } 

     return currStack; 
}