encode/decode Binary Tree, preorder+"X"，要test，寫完還有時間問怎麼verify兩個tree一樣比較好
第一轮serialized deserialize tree秒 印度小哥
followup，n-nary tree，
每个node val变成str，怎么分割，（hash成int再存）
---
第一轮：
Serialize and Deserialize Tree
两种解法：
1）先记录preorder和inorder，相同数字的node特殊处理，再构建
2）一般操作，inorder遍历，用null
Follow up的几个小问题：
1）如果node不是数字而是任意字符串怎么办，可以抽象为如何serialize and deserialize String[].
解法1：把所有*替换成**再用“ * ”(有两个空格)作为分隔符
解法2：利用TCP的思想，在之前先记录每个字符的长度
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildStr(root,sb);
return sb.toString();
}
private void buildStr(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("N,");
return;
}
sb.append(root.val + ",");
buildStr(root.left,sb);
buildStr(root.right,sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] strs = data.split(",");
return buildTree(strs, new int[]{0});
}
private TreeNode buildTree(String[] strs, int[] index) {
if (strs[index[0]].equals("N")) {
index[0]++;
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(strs[index[0]]));
index[0]++;
root.left = buildTree(strs,index);
root.right = buildTree(strs,index);
return root;
}
}
using pre+in
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder,inorder,0,inorder.length - 1);
}
int index = 0;
private TreeNode build(int[] preorder, int[] inorder, int start, int end) {
if (start > end) return null;
//System.out.println(preorder[index]);
//System.out.println(preorder[index]);
int curIndex = -1;
for (int i = start; i <= end; i++) {
if (inorder[i] == preorder[index]) {
curIndex = i;
break;
}
}
TreeNode root = new TreeNode(preorder[index]);
index++;
root.left = build(preorder,inorder,start,curIndex - 1);
root.right = build(preorder,inorder,curIndex + 1,end);
return root;
}
}
using level order
public class Codec {
public String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
if (cur == null) {
sb.append("N,");
continue;
} else {
sb.append(cur.val + ",");
}
q.offer(cur.left);
q.offer(cur.right);
}
// int i = sb.length()-1;
// while (sb.charAt(i) == 'N' || sb.charAt(i) == ',') i--;
// return sb.substring(0,i+2).toString();
return sb.toString();
}
public TreeNode deserialize(String data) {
if (data.equals("")) return null;
String[] strs = data.split(",");
Queue<String> q = new LinkedList<>(Arrays.asList(strs));
Queue<TreeNode> nodeq = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(q.poll()));
nodeq.offer(root);
while (!nodeq.isEmpty()) {
TreeNode cur = nodeq.poll();
TreeNode left = null;
TreeNode right = null;
if (!q.isEmpty() && !q.peek().equals("N")) {
left= new TreeNode(Integer.parseInt(q.poll()));
nodeq.offer(left);
} else {
q.poll();
}
if (!q.isEmpty() && !q.peek().equals("N")) {
right= new TreeNode(Integer.parseInt(q.poll()));
nodeq.offer(right);
} else {
q.poll();
}
cur.left = left;
cur.right = right;
}
return root;
}
}
n-array record # of children
class Codec {
public String serialize(Node root) {
if (root == null) return "";
StringBuilder str = new StringBuilder();
buildStr(root, str);
return str.toString();
}
public void buildStr(Node root, StringBuilder str) {
str.append(root.val+","+ root.children.size()+",");
for (Node child: root.children) {
buildStr(child, str);
}
}
// Decodes your encoded data to tree.
public Node deserialize(String data) {
if (data == "") return null;
String[] strs = data.split(",");
Queue<String> queue = new LinkedList<>(Arrays.asList(strs));
return buildTree(queue);
}
public Node buildTree(Queue<String> queue) {
int cur = Integer.parseInt(queue.poll());
int childrenNum = Integer.parseInt(queue.poll());
List<Node> children = new ArrayList<>();
Node node = new Node(cur, children);
for (int i = 0; i < childrenNum; i++) {
children.add(buildTree(queue));
}
return node;
}
}
n-array use 1,[3,[5,6],2,4,]
class Codec {
public String serialize(Node root) {
if (root == null) return "";
StringBuilder str = new StringBuilder();
buildStr(root, str);
return str.toString();
}
public void buildStr(Node root, StringBuilder str) {
str.append(root.val+",[,");
for (Node child: root.children) {
buildStr(child, str);
}
str.append("],");
}
// Decodes your encoded data to tree.
public Node deserialize(String data) {
if (data == "") return null;
String[] strs = data.split(",");
Queue<String> queue = new LinkedList<>(Arrays.asList(strs));
return buildTree(queue);
}
public Node buildTree(Queue<String> queue) {
Node root = new Node(Integer.parseInt(queue.poll()),new ArrayList<>());
Deque<Node> stack = new ArrayDeque<>();
Node cur = root;
while (!queue.isEmpty()) {
if (queue.peek().equals("[")) {
stack.push(cur);
queue.poll();
} else if (queue.peek().equals("]")) {
stack.pop();
queue.poll();
} else {
cur = new Node(Integer.parseInt(queue.poll()),new ArrayList<>());
stack.peek().children.add(cur);
}
}
return root;
}
}