बाइनरी खोज पेड़ में केवल 1 के बने रूट से गहरा पथ कैसे खोजें?

Question

हमारे पास केवल 0 और 1 एस से बना एक बाइनरी पेड़ (बीएसटी नहीं) है। हम जड़ से एक पथ के साथ गहरे 1 खोजने की जरूरत है केवल से बना 1 के

स्रोत: अमेज़न साक्षात्कार क्यू

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

तो नोड आप पर हैं एक '0', फिर 'की गहराई है 1 है 0. अन्यथा, यदि आप जिस नोड पर हैं, वह '1' है, तो अपने बाएं और दाएं बच्चों दोनों की अधिकतम 'किसी की गहराई' में 1 जोड़ें - और उनमें से अधिकतम को वापस करें।

ऊपर कोड लंबाई पाता है, मार्ग के किनारे वास्तविक नोड्स लगता है, तो आप इस

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