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 "";
- }
- List<String> list = new ArrayList();
- serializeHelper(list, root);
- return String.join(",", list);
- }
- private void serializeHelper(List<String> list, TreeNode node) {
- if (node == null) {
- return;
- }
- list.add(String.valueOf(node.val));
- serializeHelper(list, node.left);
- serializeHelper(list, node.right);
- }
- // Decodes your encoded data to tree.
- public TreeNode deserialize(String data) {
- if (data == null || data.length() == 0) {
- return null;
- }
- // Queue<String> queue = new LinkedList(Arrays.asList(data.split(",")));
- // return deserializeHelper(queue, Integer.MIN_VALUE, Integer.MAX_VALUE);
- List<String> list = Arrays.asList(data.split(","));
- return deserializeHelper(list, new int[1], Integer.MIN_VALUE, Integer.MAX_VALUE);
- }
- // This helper function uses queue to construct the tree.
- private TreeNode deserializeHelper(Queue<String> queue, int min, int max) {
- if (queue == null || queue.isEmpty()) {
- return null;
- }
- int valToBeInserted = Integer.parseInt(queue.peek());
- if (valToBeInserted < min || valToBeInserted > max) {
- return null;
- }
- queue.poll();
- TreeNode node = new TreeNode(valToBeInserted);
- node.left = deserializeHelper(queue, min, valToBeInserted);
- node.right = deserializeHelper(queue, valToBeInserted, max);
- return node;
- }
- // This helper function uses list and index to construct the tree.
- private TreeNode deserializeHelper(List<String> list, int[] index, int min, int max) {
- if (index[0] == list.size()) {
- return null;
- }
- int valToBeInserted = Integer.parseInt(list.get(index[0]));
- if (valToBeInserted < min || valToBeInserted > max) {
- return null;
- }
- index[0]++;
- TreeNode node = new TreeNode(valToBeInserted);
- node.left = deserializeHelper(list, index, min, valToBeInserted);
- node.right = deserializeHelper(list, index, valToBeInserted, max);
- 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