add 599

fishercoder1534 · fishercoder1534 · commit 9b84a2fe9a48 · 2019-01-03T10:30:13.000-08:00
diff --git a/README.md b/README.md
@@ -223,6 +223,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |562|[Longest Line of Consecutive One in Matrix](https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_562.java) | O(m*n) |O(m*n) | |Medium | Matrix DP
 |561|[Array Partition I](https://leetcode.com/problems/array-partition-i/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_561.java) | O(nlogn) |O(1) | |Easy | Array
 |560|[Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_560.java) | O(n) |O(n) || Medium | Array, HashMap
+|559|[Maximum Depth of N-ary Tree](https://leetcode.com/problems/maximum-depth-of-n-ary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_559.java) | O(n) |O(n) | |Easy | DFS, recursion
 |557|[Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_557.java) | O(n) |O(n) | |Easy | String
 |556|[Next Greater Element III](https://leetcode.com/problems/parents-greater-element-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/NextGreaterElementIII.java) | O(n)|O(1)| |Medium | String
 |555|[Split Concatenated Strings](https://leetcode.com/problems/split-concatenated-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_555.java) | O(n^2) |O(n) | |Medium | String
diff --git a/src/main/java/com/fishercoder/solutions/_559.java b/src/main/java/com/fishercoder/solutions/_559.java
@@ -0,0 +1,60 @@
+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));
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_559Test.java b/src/test/java/com/fishercoder/_559Test.java
@@ -0,0 +1,33 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.Node;
+import com.fishercoder.solutions._559;
+import java.util.Arrays;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _559Test {
+  private static _559.Solution1 solution1;
+  private static Node root;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _559.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    root = new Node(1);
+    Node node3 = new Node(3);
+    Node node2 = new Node(2);
+    Node node4 = new Node(4);
+    root.children = Arrays.asList(node3, node2, node4);
+    Node node5 = new Node(5);
+    Node node6 = new Node(6);
+    node3.children = Arrays.asList(node5, node6);
+
+    assertEquals(3, solution1.maxDepth(root));
+  }
+}
