package com.fishercoder.solutions;

import com.fishercoder.common.classes.Node;
import java.util.ArrayList;
import java.util.List;

/**
 * 559. Maximum Depth of N-ary Tree
 *
 * Given a n-ary tree, find its maximum depth.
 *
 * The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
 *
 * For example, given a 3-ary tree:
 *                            1
 *                          / | \
 *                         3  2  4
 *                        / \
 *                       5  6
 *
 * We should return its max depth, which is 3.
 *
 * Note:
 *
 * The depth of the tree is at most 1000.
 * The total number of nodes is at most 5000.
 */
public class _559 {
  public static class Solution1 {
    public int maxDepth(Node root) {
      int maxDepth = 0;
      if (root == null) {
        return maxDepth;
      }
      List<List<Integer>> allPaths = new ArrayList<>();
      List<Integer> currentPath = new ArrayList<>();
      dfs(root, currentPath, allPaths);
      for (List<Integer> path : allPaths) {
        maxDepth = Math.max(path.size(), maxDepth);
      }
      return maxDepth;
    }

    private void dfs(Node root, List<Integer> currentPath, List<List<Integer>> allPaths) {
      if (root == null) {
        allPaths.add(new ArrayList<>(currentPath));
      }
      if (root.children != null && !root.children.isEmpty()) {
        currentPath.add(root.val);
        for (Node child : root.children) {
          dfs(child, new ArrayList<>(currentPath), allPaths);
        }
      }
      if (root.children == null || root.children.isEmpty()) {
        currentPath.add(root.val);
        allPaths.add(new ArrayList<>(currentPath));
      }
    }
  }
}

@@ -73,16 +73,17 @@
 s.Node;%0A
+%0A
 import j
@@ -130,576 +130,8 @@
 t;%0A%0A
-/**%0A * 559. Maximum Depth of N-ary Tree%0A *%0A * Given a n-ary tree, find its maximum depth.%0A *%0A * The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.%0A *%0A * For example, given a 3-ary tree:%0A *                            1%0A *                          / %7C %5C%0A *                         3  2  4%0A *                        / %5C%0A *                       5  6%0A *%0A * We should return its max depth, which is 3.%0A *%0A * Note:%0A *%0A * The depth of the tree is at most 1000.%0A * The total number of nodes is at most 5000.%0A */%0A
 publ
@@ -146,16 +146,18 @@
  _559 %7B%0A
+  
   public
@@ -182,16 +182,20 @@
 tion1 %7B%0A
+    
     publ
@@ -229,16 +229,22 @@
 %7B%0A      
+  
+    
 int maxD
@@ -255,24 +255,30 @@
  = 0;%0A      
+  
+    
 if (root == 
@@ -289,24 +289,32 @@
 ) %7B%0A        
+  
+      
 return maxDe
@@ -320,26 +320,38 @@
 epth;%0A      
-%7D%0A
+      %7D%0A      
       List%3CL
@@ -396,24 +396,30 @@
 %3C%3E();%0A      
+     
+ 
 List%3CInteger
@@ -449,24 +449,30 @@
 ayList%3C%3E();%0A
+      
       dfs(ro
@@ -501,24 +501,30 @@
 ths);%0A      
+     
+ 
 for (List%3CIn
@@ -545,24 +545,32 @@
 allPaths) %7B%0A
+        
         maxD
@@ -611,26 +611,38 @@
 pth);%0A      
+   
-%7D%0A
+   %7D%0A      
       return
@@ -660,11 +660,19 @@
     
-%7D%0A%0A
+    %7D%0A%0A    
     
@@ -754,24 +754,30 @@
 allPaths) %7B%0A
+      
       if (ro
@@ -782,32 +782,40 @@
 root == null) %7B%0A
+        
         allPaths
@@ -852,26 +852,38 @@
 th));%0A      
+    
-%7D%0A
+  %7D%0A      
       if (ro
@@ -933,32 +933,40 @@
 ty()) %7B%0A        
+    
+    
 currentPath.add(
@@ -968,32 +968,40 @@
 .add(root.val);%0A
+        
         for (Nod
@@ -1023,24 +1023,34 @@
 children) %7B%0A
+          
           df
@@ -1107,24 +1107,46 @@
         
+ 
+       %7D%0A            
 %7D%0A      
 %7D%0A      
@@ -1133,26 +1133,24 @@
     %7D%0A      
-%7D%0A
       if (ro
@@ -1199,32 +1199,40 @@
 ty()) %7B%0A        
+     
+   
 currentPath.add(
@@ -1234,32 +1234,40 @@
 .add(root.val);%0A
+        
         allPaths
@@ -1312,16 +1312,28 @@
     
+      %7D%0A        
 %7D%0A  
-  %7D%0A
   %7D%0A

refactor 559