Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- /*
- Serialize function
- Time Complexity: O(M * K) = O(M * 11) = O(M)
- Space Complexity: O(M * K) = O(M * 11) = O(M)
- M = Number of Nodes
- K = Average Length of each node. (Bounded by 11)
- Deserialize function
- Time Complexity: O(N + M + M*K) = O(N + M*K) = O(N+N) = O(N)
- Space Complexity: O(M * K) = O(N)
- N = Length of the input string
- M = Number of Nodes
- K = Average Length of each node. (Bounded by 11)
- */
- public class Codec {
- // Encodes a tree to a single string.
- public String serialize(TreeNode root) {
- if (root == null) {
- return "#";
- }
- StringBuilder sb = new StringBuilder();
- serializeHelper(sb, root);
- System.out.println(sb.toString());
- return sb.toString();
- }
- private void serializeHelper(StringBuilder sb, TreeNode node) {
- if (node == null) {
- sb.append("#");
- return;
- }
- sb.append(node.val).append(",");
- serializeHelper(sb, node.left);
- sb.append(",");
- serializeHelper(sb, node.right);
- }
- // Decodes your encoded data to tree.
- public TreeNode deserialize(String data) {
- if (data == null || data.length() == 0) {
- return null;
- }
- return deserializeHelper(new LinkedList<String>(Arrays.asList(data.split(","))));
- }
- private TreeNode deserializeHelper(Queue<String> queue) {
- if (queue.isEmpty()) {
- return null;
- }
- String valToBeAdded = queue.poll();
- if ("#".equals(valToBeAdded) || valToBeAdded.length() == 0) {
- return null;
- }
- TreeNode node = new TreeNode(Integer.parseInt(valToBeAdded));
- node.left = deserializeHelper(queue);
- node.right = deserializeHelper(queue);
- return node;
- }
- }
- // Your Codec object will be instantiated and called as such:
- // Codec codec = new Codec();
- // codec.deserialize(codec.serialize(root));
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement