Skip to content

add solution and test cases for 449 #143

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Jan 9, 2021
Merged

add solution and test cases for 449 #143

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
40 changes: 40 additions & 0 deletions src/main/java/com/fishercoder/solutions/_449.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,6 +2,7 @@

import com.fishercoder.common.classes.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

Expand Down Expand Up @@ -150,4 +151,43 @@ public TreeNode deserialize(String data) {
return root;
}
}
public static class Solution4 {
private static final String NULL_SYMBOL = "X";
private static final String DELIMITER = ",";

// Encodes a tree to a single string.
public String serialize(TreeNode root) {

// If we have a null symbol, encode it to NULL_SYMBOL
if(root == null)
return NULL_SYMBOL + DELIMITER;

String leftSubtree = serialize(root.left);
String rightSubtree = serialize(root.right);

return root.val + DELIMITER + leftSubtree + rightSubtree;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {

Queue<String> nodesLeftToSerialize = new LinkedList<>();
nodesLeftToSerialize.addAll(Arrays.asList(data.split(DELIMITER)));
return deserializeHelper(nodesLeftToSerialize);

}
private TreeNode deserializeHelper(Queue<String> nodesLeft){

// remove the node
String nodeLeftToSerialize = nodesLeft.poll();
// base case
if(nodeLeftToSerialize.equals(NULL_SYMBOL)){
return null;
}
TreeNode newNode = new TreeNode(Integer.valueOf(nodeLeftToSerialize));
newNode.left = deserializeHelper(nodesLeft);
newNode.right = deserializeHelper(nodesLeft);
return newNode;
}
}
}
4 changes: 4 additions & 0 deletions src/test/java/com/fishercoder/_449Test.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,13 +12,15 @@ public class _449Test {
private static _449.Solution1 solution1;
private static _449.Solution2 solution2;
private static _449.Solution3 solution3;
private static _449.Solution4 solution4;
private static TreeNode expectedRoot;

@BeforeClass
public static void setup() {
solution1 = new _449.Solution1();
solution2 = new _449.Solution2();
solution3 = new _449.Solution3();
solution4 = new _449.Solution4();
}

@Before
Expand All @@ -34,6 +36,7 @@ public void test1() {
assertEquals(expectedRoot.toString(), solution1.deserialize(solution1.serialize(expectedRoot)).toString());
assertEquals(expectedRoot.toString(), solution2.deserialize(solution2.serialize(expectedRoot)).toString());
assertEquals(expectedRoot.toString(), solution3.deserialize(solution3.serialize(expectedRoot)).toString());
assertEquals(expectedRoot.toString(), solution4.deserialize(solution4.serialize(expectedRoot)).toString());
}

@Test
Expand All @@ -44,5 +47,6 @@ public void test2() {
assertEquals(expectedRoot.toString(), solution1.deserialize(solution1.serialize(expectedRoot)).toString());
assertEquals(expectedRoot.toString(), solution2.deserialize(solution2.serialize(expectedRoot)).toString());
assertEquals(expectedRoot.toString(), solution3.deserialize(solution3.serialize(expectedRoot)).toString());
assertEquals(expectedRoot.toString(), solution4.deserialize(solution4.serialize(expectedRoot)).toString());
}
}