#34. Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level) as a list of lists.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
int level;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
root.level = 0;
int currentLevel = 0;
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> partialRes = new ArrayList<>();
while (!queue.isEmpty()) {
if (queue.peek().level == currentLevel) {
TreeNode node = queue.poll();
partialRes.add(node.val);
if (node.left != null) {
node.left.level = currentLevel + 1;
queue.add(node.left);
}
if (node.right != null) {
node.right.level = currentLevel + 1;
queue.add(node.right);
}
} else {
currentLevel++;
break;
}
}
if (!partialRes.isEmpty()) {
result.add(partialRes);
}
}
return result;
}
}
#35. Serialize & Deserialize Binary Tree
Serialization is the process of 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. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
! exceeds memory limit for larger sets of data
public class Codec {
// Encodes a tree to a single string --->> scris ca arbore complet "1,2,3,null,4"
public String serialize(TreeNode root) {
StringBuilder serial = new StringBuilder();
Map<Integer, Integer> posVal = new HashMap<>();
buildPosVal(root, 0, posVal);
Optional<Integer> maxPos = posVal.keySet().stream().max(Integer::compare);
if (!maxPos.isPresent()) {
return "";
}
int highestOneBit = Integer.highestOneBit(maxPos.get() + 1);
int len;
switch (highestOneBit) {
case 0:
len = 1;
break;
case 1:
len = 3;
break;
default:
len = highestOneBit * 2 - 1;
}
for (int i=0; i<len; i++) {
serial.append(posVal.containsKey(i) ? posVal.get(i)+"" : "N").append(",");
}
return serial.toString();
}
private void buildPosVal(TreeNode node, Integer level, Map<Integer, Integer> posVal) {
if (node == null) {
return;
}
posVal.put(level, node.val);
buildPosVal(node.left, 2 * level + 1, posVal);
buildPosVal(node.right, 2 * level + 2, posVal);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length() <= 1) {
return null;
}
String str[] = data.split(",");
return buildFrom(new TreeNode(str[0]), 0, str);
}
private TreeNode buildFrom(TreeNode treeElem, int k, String[] elements) {
if (treeElem == null) {
return null;
}
if (elements.length > 2 * k + 1 && !"N".equals(elements[2 * k + 1])) {
TreeNode left = new TreeNode(elements[2 * k + 1]);
treeElem.left = buildFrom(left, 2 * k + 1, elements);
}
if (elements.length > 2 * k + 2 && !"N".equals(elements[2 * k + 2])) {
TreeNode right = new TreeNode(elements[2 * k + 2]);
treeElem.right = buildFrom(right, 2 * k + 2, elements);
}
return treeElem;
}
}
! slightly better BUT not good enough :(
class TreeNode {
int val;
TreeNode left;
TreeNode right;
int index;
TreeNode(int x) { val = x; }
}
public class Codec {
// Encodes a tree to a single string --->> scris ca arbore complet "0=1,1=2,2=3,3=null,4=4"
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
root.index = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
StringBuilder serial = new StringBuilder();
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
addDataWithFilling(serial, node);
if (node.left != null) {
node.left.index = 2 * node.index + 1;
queue.add(node.left);
}
if (node.right != null) {
node.right.index = 2 * node.index + 2;
queue.add(node.right);
}
}
return serial.toString();
}
private void addDataWithFilling(StringBuilder serial, TreeNode node) {
int lastIndex = serial.toString().lastIndexOf(",");
if (lastIndex > -1) {
int beforeLastIndex = serial.toString().substring(0, lastIndex).lastIndexOf(",");
String lastData = beforeLastIndex > -1 ?
serial.toString().substring(beforeLastIndex + 1, lastIndex) :
serial.toString().substring(0, lastIndex);
int lastPos = extractIndexFromData(lastData);
for (int i=lastPos+1; i<node.index; i++) {
serial.append(node.index + "=N,"); // null
}
}
serial.append(node.index + "=" + node.val + ",");
}
private int extractIndexFromData(String data) {
return Integer.parseInt(data.substring(0, data.indexOf("=")));
}
private Integer extractValueFromData(String data) {
try {
return Integer.parseInt(data.substring(data.indexOf("=") + 1));
} catch(Exception e) {
return null;
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
// idem
}
}
! accepted with good memory usage
public class Codec {
// Encodes a tree to a single string --->> scris ca arbore complet "1,2,N,N,3,4,N,N,5,N,N,"
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
sb.append(root.val).append(",");
String result = dfs(root, sb).toString();
return result;
}
private StringBuilder dfs(TreeNode node, StringBuilder serial) {
if (node.left != null) {
serial.append(node.left.val).append(",");
serial = dfs(node.left, serial);
} else {
serial.append("N,");
}
if (node.right != null) {
serial.append(node.right.val).append(",");
serial = dfs(node.right, serial);
} else {
serial.append("N,");
}
return serial;
}
private Integer extractValueFromData(String data) { // data = "val,....." => val
int indexStop = data.indexOf(",");
if (indexStop > -1) {
try {
return Integer.parseInt(data.substring(0, indexStop));
} catch(Exception e) {
return null;
}
}
return null;
}
private void updateSerial() { // remove first record
int commaIndex = serial.indexOf(",");
if (commaIndex > -1) {
serial = serial.substring(commaIndex+1);
}
}
String serial;
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length() <= 1) {
return null;
}
Integer value = extractValueFromData(data);
this.serial = data;
updateSerial();
if (value != null) {
TreeNode root = new TreeNode(value);
return buildFrom(root);
}
return null;
}
private TreeNode buildFrom(TreeNode treeElem) {
if (treeElem == null) {
return null;
}
Integer value = extractValueFromData(serial);
updateSerial();
if (value != null) {
TreeNode left = new TreeNode(value);
treeElem.left = buildFrom(left);
}
value = extractValueFromData(serial);
updateSerial();
if (value != null) {
TreeNode right = new TreeNode(value);
treeElem.right = buildFrom(right);
}
return treeElem;
}
}
