package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 111. Minimum Depth of Binary Tree
 *
 * Given a binary tree, find its minimum depth.
 * The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
 * */

public class _111 {
    public static class Solution1 {
      /**DFS*/
      public int minDepth(TreeNode root) {
        if (root == null) {
          return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0) {
          return right + 1;
        }
        if (right == 0) {
          return left + 1;
        }
        return Math.min(left, right) + 1;
      }
    }

  public static class Solution2 {
    /**BFS*/
    public int minDepth(TreeNode root) {
      if (root == null) {
        return 0;
      }
      Queue<TreeNode> q = new LinkedList();
      q.offer(root);
      int level = 0;
      while (!q.isEmpty()) {
        level++;
        int size = q.size();
        for (int i = 0; i < size; i++) {
          TreeNode curr = q.poll();
          if (curr.left != null) {
            q.offer(curr.left);
          }
          if (curr.right != null) {
            q.offer(curr.right);
          }
          if (curr.left == null && curr.right == null) {
            return level;
          }
        }
      }
      return level;
    }
  }
}

@@ -136,225 +136,8 @@
 e;%0A%0A
-/**%0A * 111. Minimum Depth of Binary Tree%0A *%0A * Given a binary tree, find its minimum depth.%0A * The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.%0A * */%0A%0A
 publ
@@ -198,17 +198,43 @@
     
+  
 /**
-DFS
+%0A         * DFS%0A         
 */%0A
+  
     
@@ -276,24 +276,28 @@
 ) %7B%0A        
+    
 if (root == 
@@ -306,32 +306,38 @@
 ll) %7B%0A          
+   
+   
 return 0;%0A      
@@ -330,32 +330,36 @@
 turn 0;%0A        
+    
 %7D%0A        int le
@@ -348,24 +348,28 @@
   %7D%0A        
+ 
+   
 int left = m
@@ -380,32 +380,36 @@
 pth(root.left);%0A
+    
         int righ
@@ -438,24 +438,28 @@
 t);%0A        
+ 
+   
 if (left == 
@@ -455,32 +455,38 @@
 f (left == 0) %7B%0A
+      
           return
@@ -497,34 +497,42 @@
 ht + 1;%0A        
-%7D%0A
+    %7D%0A    
         if (righ
@@ -543,32 +543,38 @@
  0) %7B%0A          
+      
 return left + 1;
@@ -574,34 +574,42 @@
 ft + 1;%0A        
+   
+ 
 %7D%0A
+    
         return M
@@ -636,24 +636,26 @@
  + 1;%0A      
+  
 %7D%0A    %7D%0A%0A  p
@@ -653,16 +653,18 @@
    %7D%0A%0A  
+ 
+ 
 public s
@@ -695,17 +695,47 @@
     
-/**BFS*/%0A
+    /**%0A         * BFS%0A         */%0A    
     
@@ -773,24 +773,30 @@
 ot) %7B%0A      
+  
+    
 if (root == 
@@ -795,32 +795,40 @@
 root == null) %7B%0A
+        
         return 0
@@ -831,26 +831,38 @@
 rn 0;%0A      
+     
+ 
 %7D%0A
+      
       Queue%3C
@@ -889,24 +889,30 @@
 nkedList();%0A
+      
       q.offe
@@ -922,24 +922,30 @@
 oot);%0A      
+   
+   
 int level = 
@@ -943,24 +943,30 @@
  level = 0;%0A
+      
       while 
@@ -978,24 +978,32 @@
 sEmpty()) %7B%0A
+        
         leve
@@ -1007,16 +1007,24 @@
 evel++;%0A
+        
         
@@ -1040,24 +1040,32 @@
 = q.size();%0A
+        
         for 
@@ -1089,24 +1089,34 @@
 ize; i++) %7B%0A
+          
           Tr
@@ -1141,32 +1141,42 @@
 ll();%0A          
+       
+   
 if (curr.left !=
@@ -1176,32 +1176,44 @@
 left != null) %7B%0A
+            
             q.of
@@ -1230,34 +1230,52 @@
 eft);%0A          
+ 
-%7D%0A
+         %7D%0A        
           if (cu
@@ -1260,32 +1260,34 @@
                 
+  
 if (curr.right !
@@ -1288,32 +1288,44 @@
 ight != null) %7B%0A
+            
             q.of
@@ -1343,34 +1343,54 @@
 ght);%0A          
+  
-%7D%0A
+        %7D%0A          
           if (cu
@@ -1422,32 +1422,44 @@
 ight == null) %7B%0A
+            
             retu
@@ -1482,28 +1482,58 @@
     
+   
-%7D%0A        %7D%0A      %7D%0A
+       %7D%0A                %7D%0A            %7D%0A      
     
@@ -1552,16 +1552,22 @@
 el;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 111