add leetcode (examplehub#137)

realDuYuanChao · github-actions · web-flow · commit 5c64a8ef49e1 · 2021-07-18T20:42:41.000+08:00
* remove-duplicates-from-sorted-array

* fixme comment

* test if binary tree is same
add binary tree utils
binary tree level order traversal

* Formatted with Google Java Formatter

Co-authored-by: github-actions &lt;${GITHUB_ACTOR}@users.noreply.github.com&gt;
diff --git a/src/main/java/com/examplehub/leetcode/easy/SameTree.java b/src/main/java/com/examplehub/leetcode/easy/SameTree.java
@@ -0,0 +1,19 @@
+package com.examplehub.leetcode.easy;
+
+import com.examplehub.leetcode.TreeNode;
+
+/** https://leetcode.com/problems/same-tree/ */
+public class SameTree {
+  public static boolean solution1(TreeNode p, TreeNode q) {
+    if (p == null && q == null) {
+      return true;
+    }
+    if (p == null || q == null) {
+      return false;
+    }
+    if (p.val != q.val) {
+      return false;
+    }
+    return solution1(p.left, q.left) && solution1(p.right, q.right);
+  }
+}
diff --git a/src/main/java/com/examplehub/leetcode/middle/BinaryTreeLevelOrderTraversal.java b/src/main/java/com/examplehub/leetcode/middle/BinaryTreeLevelOrderTraversal.java
@@ -6,6 +6,7 @@
 import java.util.List;
 import java.util.Queue;
 
+/** https://leetcode.com/problems/binary-tree-level-order-traversal/ */
 public class BinaryTreeLevelOrderTraversal {
   public static List<List<Integer>> solution1(TreeNode root) {
     if (root == null) {
diff --git a/src/main/java/com/examplehub/leetcode/utils/BinaryTreeUtils.java b/src/main/java/com/examplehub/leetcode/utils/BinaryTreeUtils.java
@@ -0,0 +1,16 @@
+package com.examplehub.leetcode.utils;
+
+import com.examplehub.leetcode.TreeNode;
+
+public class BinaryTreeUtils {
+  public static TreeNode createTree(int[] nodes, int i) {
+    int numberOfNodes = nodes.length;
+    if (i >= numberOfNodes || nodes[i] == -1) {
+      return null;
+    }
+    TreeNode root = new TreeNode(nodes[i]);
+    root.left = createTree(nodes, i * 2 + 1);
+    root.right = createTree(nodes, i * 2 + 2);
+    return root;
+  }
+}
diff --git a/src/test/java/com/examplehub/leetcode/easy/SameTreeTest.java b/src/test/java/com/examplehub/leetcode/easy/SameTreeTest.java
@@ -0,0 +1,27 @@
+package com.examplehub.leetcode.easy;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.examplehub.leetcode.TreeNode;
+import com.examplehub.leetcode.utils.BinaryTreeUtils;
+import org.junit.jupiter.api.Test;
+
+class SameTreeTest {
+  @Test
+  void testSolution1() {
+    TreeNode firstTree = BinaryTreeUtils.createTree(new int[] {1, 2, 3}, 0);
+    TreeNode secondTree = BinaryTreeUtils.createTree(new int[] {1, 2, 3}, 0);
+    assertTrue(SameTree.solution1(firstTree, secondTree));
+
+    firstTree = BinaryTreeUtils.createTree(new int[] {1, 2}, 0);
+    secondTree = BinaryTreeUtils.createTree(new int[] {1, -1, 2}, 0);
+    assertFalse(SameTree.solution1(firstTree, secondTree));
+
+    firstTree = BinaryTreeUtils.createTree(new int[] {1, 2, 1}, 0);
+    secondTree = BinaryTreeUtils.createTree(new int[] {1, 1, 2}, 0);
+    assertFalse(SameTree.solution1(firstTree, secondTree));
+
+    assertFalse(SameTree.solution1(null, firstTree));
+    assertFalse(SameTree.solution1(null, secondTree));
+  }
+}
diff --git a/src/test/java/com/examplehub/leetcode/middle/BinaryTreeLevelOrderTraversalTest.java b/src/test/java/com/examplehub/leetcode/middle/BinaryTreeLevelOrderTraversalTest.java
@@ -2,11 +2,18 @@
 
 import static org.junit.jupiter.api.Assertions.*;
 
+import com.examplehub.leetcode.TreeNode;
+import com.examplehub.leetcode.utils.BinaryTreeUtils;
 import org.junit.jupiter.api.Test;
 
 class BinaryTreeLevelOrderTraversalTest {
   @Test
   void testSolution1() {
-    // TODO
+    TreeNode root = BinaryTreeUtils.createTree(new int[] {3, 9, 20, -1, -1, 15, 7}, 0);
+    assertEquals(
+        "[[3], [9, 20], [15, 7]]", BinaryTreeLevelOrderTraversal.solution1(root).toString());
+
+    root = BinaryTreeUtils.createTree(new int[] {1}, 0);
+    assertEquals("[[1]]", BinaryTreeLevelOrderTraversal.solution1(root).toString());
   }
 }
diff --git a/src/test/java/com/examplehub/leetcode/utils/BinaryTreeUtilsTest.java b/src/test/java/com/examplehub/leetcode/utils/BinaryTreeUtilsTest.java
@@ -0,0 +1,17 @@
+package com.examplehub.leetcode.utils;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.examplehub.leetcode.TreeNode;
+import org.junit.jupiter.api.Test;
+
+class BinaryTreeUtilsTest {
+  @Test
+  void test() {
+    TreeNode root = BinaryTreeUtils.createTree(new int[] {1, 2, 3}, 0);
+    assert root != null;
+    assertEquals(1, root.val);
+    assertEquals(2, root.left.val);
+    assertEquals(3, root.right.val);
+  }
+}
