-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution.java
88 lines (77 loc) · 2.8 KB
/
Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package serializedeserializeBST;
import datastructures.TreeNode;
import java.util.ArrayDeque;
/**
* Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
* <p>
* Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.
* <p>
* The encoded string should be as compact as possible.
* <p>
* <p>
* <p>
* Example 1:
* <p>
* Input: root = [2,1,3]
* Output: [2,1,3]
* Example 2:
* <p>
* Input: root = []
* Output: []
* <p>
* <p>
* Constraints:
* <p>
* The number of nodes in the tree is in the range [0, 104].
* 0 <= Node.val <= 104
* The input tree is guaranteed to be a binary search tree.
* <p>
* Runtime: 12 ms, faster than 38.97% of Java online submissions for Serialize and Deserialize BST.
* Memory Usage: 40.5 MB, less than 7.96% of Java online submissions for Serialize and Deserialize BST.
*/
class Solution {
// create postorder traversal & store it in SB
private StringBuilder postorder(TreeNode root, StringBuilder sb) {
if (root == null)
return sb;
postorder(root.left, sb);
postorder(root.right, sb);
sb.append(root.val);
sb.append(' ');
return sb;
}
// Encodes a tree to a single string.
String serialize(TreeNode root) {
StringBuilder sb = postorder(root, new StringBuilder());
if (sb.length() > 0)
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
// Decodes your encoded data to tree.
TreeNode deserialize(String data) {
if (data.isEmpty())
return null;
ArrayDeque<Integer> nums = new ArrayDeque<Integer>();
for (String s : data.split("\\s+"))
nums.add(Integer.valueOf(s));
return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, nums);
}
private TreeNode helper(Integer lower, Integer upper, ArrayDeque<Integer> nums) {
if (nums.isEmpty())
return null;
int val = nums.getLast();
if (val < lower || val > upper)
return null;
nums.removeLast();
TreeNode root = new TreeNode(val);
root.right = helper(val, upper, nums);
root.left = helper(lower, val, nums);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;