add 589

fishercoder1534 · fishercoder1534 · commit d8e67fd4a7e7 · 2018-12-21T08:25:44.000-08:00
diff --git a/README.md b/README.md
@@ -191,6 +191,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |593|[Valid Square](https://leetcode.com/problems/valid-square/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_593.java) | O(1) |O(1) | |Medium | Math
 |592|[Fraction Addition and Subtraction](https://leetcode.com/problems/fraction-addition-and-subtraction/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_592.java) | O(nlogx) |O(n) | |Medium | Math
 |591|[Tag Validator](https://leetcode.com/problems/tag-validator/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_591.java) | O(n) |O(n) | |Hard | Stack, String
+|589|[N-ary Tree Preorder Traversal](https://leetcode.com/problems/n-ary-tree-preorder-traversal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_589.java) | O(n) |O(n) | |Easy | DFS, recursion
 |588|[Design In-Memory File System](https://leetcode.com/problems/design-in-memory-file-system/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_588.java) | O(n) |O(h) | |Hard | Trie, Design
 |587|[Erect the Fence](https://leetcode.com/problems/erect-the-fence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_587.java) | O(?) |O(?) | |Hard | Geometry
 |583|[Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_583.java) | O(m*n) |O(m*n) could be optimized to O(n) | |Medium | DP
diff --git a/src/main/java/com/fishercoder/common/classes/Node.java b/src/main/java/com/fishercoder/common/classes/Node.java
@@ -0,0 +1,22 @@
+package com.fishercoder.common.classes;
+
+import java.util.List;
+
+public class Node {
+  public int val;
+  public List<Node> children;
+
+  public Node() {
+  }
+
+  public Node(int _val, List<Node> _children) {
+    val = _val;
+    children = _children;
+  }
+
+  //todo: implement this method
+  /**return a N-ary tree based on the preorder values*/
+  public static Node createNaryTree(List<Integer> preorderValues) {
+    return null;
+  }
+}
diff --git a/src/main/java/com/fishercoder/solutions/_589.java b/src/main/java/com/fishercoder/solutions/_589.java
@@ -0,0 +1,49 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.Node;
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 589. N-ary Tree Preorder Traversal
+ *
+ * Given an n-ary tree, return the preorder traversal of its nodes' values.
+ *
+ * For example, given a 3-ary tree:
+ *
+ *            1
+ *          / | \
+ *         3  2  4
+ *        / \
+ *       5   6
+ *
+ * Return its preorder traversal as: [1,3,5,6,2,4].
+ *
+ * Note:
+ *
+ * Recursive solution is trivial, could you do it iteratively?
+ */
+public class _589 {
+  public static class Solution1 {
+    public List<Integer> preorder(Node root) {
+      List<Integer> result = new ArrayList<>();
+      if (root == null) {
+        return result;
+      }
+      dfs(root, result);
+      return result;
+    }
+
+    private void dfs(Node root, List<Integer> result) {
+      if (root == null) {
+        return;
+      }
+      result.add(root.val);
+      if (root.children.size() > 0) {
+        for (Node child : root.children) {
+          dfs(child, result);
+        }
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_589Test.java b/src/test/java/com/fishercoder/_589Test.java
@@ -0,0 +1,30 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.Node;
+import com.fishercoder.solutions._589;
+import java.util.List;
+import org.junit.BeforeClass;
+import org.junit.Ignore;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+import static org.junit.Assert.assertEquals;
+
+public class _589Test {
+  private static _589.Solution1 solution1;
+  private static Node root;
+  private static List<Integer> expectedPreOrder;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _589.Solution1();
+  }
+
+  @Test
+  @Ignore//todo: Node.createNaryTree method hasn't been implemented yet
+  public void test1() {
+    expectedPreOrder = List.of(1, 3, 5, 6, 2, 4);
+    root = Node.createNaryTree(expectedPreOrder);
+    assertEquals(expectedPreOrder, solution1.preorder(root));
+  }
+}
