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 {
    /**
     * We can solve this problem using both BFS and DFS:
     * DFS is to visit every single root to leaf path and return the shortest one.
     * BFS is to visit every level and return whenever we find the first leaf node.
     */

    public static class DFSSolution {

        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 BFSSolution {

        public int minDepth_BFS(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;
        }
    }
}

@@ -173,16 +173,19 @@
 ry Tree%0A
+ *%0A
  * Given
@@ -377,286 +377,55 @@
     
-/**%0A     * We can solve this problem using both BFS and DFS:%0A     * DFS is to visit every single root to leaf path and return the shortest one.%0A     * BFS is to visit every level and return whenever we find the first leaf node.%0A     */%0A%0A    public static class DFSSolution %7B%0A%0A  
+public static class Solution1 %7B%0A      /**DFS*/%0A
     
@@ -463,36 +463,32 @@
 root) %7B%0A        
-    
 if (root == null
@@ -483,38 +483,32 @@
 root == null) %7B%0A
-      
           return
@@ -515,34 +515,26 @@
  0;%0A        
-    %7D%0A    
+%7D%0A
         int 
@@ -565,28 +565,24 @@
 t);%0A        
- 
-   
 int right = 
@@ -607,28 +607,24 @@
 t);%0A        
-    
 if (left == 
@@ -634,30 +634,24 @@
 %7B%0A          
- 
-     
 return right
@@ -652,28 +652,24 @@
  right + 1;%0A
-    
         %7D%0A  
@@ -670,28 +670,24 @@
   %7D%0A        
-    
 if (right ==
@@ -694,38 +694,32 @@
  0) %7B%0A          
-    
-  
 return left + 1;
@@ -727,33 +727,26 @@
         
-    %7D%0A   
+%7D%0A
         
  return 
@@ -733,25 +733,24 @@
   %7D%0A        
- 
 return Math.
@@ -781,20 +781,17 @@
     
-  %7D%0A
+%7D
 %0A    %7D%0A%0A
     
@@ -786,18 +786,16 @@
 %0A    %7D%0A%0A
-  
   public
@@ -812,19 +812,16 @@
 ass 
-BFS
 Solution
  %7B%0A%0A
@@ -820,16 +820,25 @@
 tion
+2
  %7B%0A
-%0A
     
+/**BFS*/%0A
     
@@ -860,12 +860,8 @@
 epth
-_BFS
 (Tre
@@ -870,30 +870,24 @@
 ode root) %7B%0A
-      
       if (ro
@@ -896,32 +896,24 @@
  == null) %7B%0A
-        
         retu
@@ -920,38 +920,26 @@
 rn 0;%0A      
-   
-   %7D%0A      
+%7D%0A
       Queue%3C
@@ -966,30 +966,24 @@
 nkedList();%0A
-      
       q.offe
@@ -993,30 +993,24 @@
 oot);%0A      
-  
-    
 int level = 
@@ -1018,22 +1018,16 @@
 ;%0A      
-     
- 
 while (!
@@ -1049,24 +1049,16 @@
         
-       
- 
 level++;
@@ -1058,24 +1058,16 @@
 evel++;%0A
-        
         
@@ -1095,24 +1095,16 @@
         
-       
- 
 for (int
@@ -1124,34 +1124,24 @@
 ize; i++) %7B%0A
-          
           Tr
@@ -1170,34 +1170,24 @@
 ;%0A          
-      
-    
 if (curr.lef
@@ -1195,36 +1195,24 @@
  != null) %7B%0A
-            
             
@@ -1241,36 +1241,18 @@
         
- 
-         %7D%0A        
+%7D%0A
         
@@ -1245,34 +1245,32 @@
     %7D%0A          
-  
 if (curr.right !
@@ -1275,36 +1275,24 @@
  != null) %7B%0A
-            
             
@@ -1322,38 +1322,18 @@
         
-  
-        %7D%0A          
+%7D%0A
         
@@ -1381,28 +1381,16 @@
 null) %7B%0A
-            
         
@@ -1421,58 +1421,28 @@
     
-   
-       %7D%0A                %7D%0A            %7D%0A      
+%7D%0A        %7D%0A      %7D%0A
     
@@ -1461,22 +1461,16 @@
 el;%0A    
-    %7D%0A  
+%7D%0A
   %7D%0A%7D%0A

refactor 111