Bir ikili arama ağacında yalnızca 1'lerden oluşan kökten en derin yolu nasıl bulunur?

Question

Sadece 0 ve 1'lerden oluşan bir ikili ağaca (BST değil) sahibiz. biz sadece yapılmış kökünden bir yol ile en derin 1 bulmalıyız 1'ler

Kaynak: Eğer üzerinde düğüm 'bir '0', ardından derinlik ise Amazon görüşme 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; 
     } 
} 

1 'dir. Aksi takdirde, üzerinde bulunduğunuz düğüm' 1 'ise, hem sol hem de sağ çocuklarınızın maksimum' birinin derinliğine '1 ekleyin ve bunların maksimumlarını döndürün.

Yukarıdaki kod yolu boyunca fiili düğümleri bulmak için, uzunluk bulur sen 1'ler en uzun dizisinin son düğümü bulmak bu

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; 
}