Intuition π
At the beginning, I was pretty confused about how to turn a tree into text. But then I had a lightbulb moment! π€― I thought, "Why not use a line and a queue?"
Approach π
So, here's what I did. First, I checked if the tree was empty. If it was, I just gave back nothing because, well, there's nothing to turn into text, right? π¬
But if there was a tree, I started a special line and a container called "StringBuilder." Think of StringBuilder as a magic box for building our text.
I put the first tree part in our container (the root) and started a loop.
In this loop, I grabbed one tree part from the front of the line. If it turned out to be empty (like a hole in the ground), I wrote "n " in our magic box (that 'n' means "nothing here").
But if there was something real, like a tree with a number on it, I wrote that number followed by a space in our magic box. Then, I put its left and right friends at the back of the line if they were there.
Complexity π€
Time complexity: O(n) - That's because we go through each tree part once when we turn it into text and when we turn it back into a tree.
Space complexity: O(n) - We use a line to keep track of tree parts, and in the worst case, it can have all the tree parts.
Code π
And here's the code that does all of this magic! It's not as tricky as it looks at first. It's all about putting tree parts in the right order and then reading them back in the same order. Simple, right? π
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
public String serialize(TreeNode root) {
if(root == null) return "";
Queue<TreeNode> queue = new LinkedList<>();
StringBuilder str = new StringBuilder();
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node == null){
str.append("n ");
continue;
}
str.append(node.val + " ");
queue.offer(node.left);
queue.offer(node.right);
}
return str.toString();
}
public TreeNode deserialize(String data) {
if (data == null || data.isEmpty()) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
String[] values = data.split(" ");
TreeNode root = new TreeNode(Integer.parseInt(values[0]));
queue.offer(root);
int i = 1;
while (i < values.length) {
TreeNode parent = queue.poll();
if (!values[i].equals("n")) {
TreeNode left = new TreeNode(Integer.parseInt(values[i]));
parent.left = left;
queue.offer(left);
}
i++;
if (!values[i].equals("n")) {
TreeNode right = new TreeNode(Integer.parseInt(values[i]));
parent.right = right;
queue.offer(right);
}
i++;
}
return root;
}
}
Happy coding,
shiva
Top comments (0)