import java.util.*;
/**
* 类似题
* https://leetcode.com/problems/serialize-and-deserialize-bst/
*/
/**
* è¦æ³¨æ„的是分隔符ä¸è¦åŠ é‡å¤äº†ï¼Œæ¯”如1,X,,Xè¿™æ ·çš„ï¼Œé‡å¤çš„è¯åœ¨split时会有空串
* 分递归版和éžé€’å½’ç‰ˆï¼Œé€’å½’ç‰ˆçš„å¦‚æžœæ ‘å¤§äº†å¯èƒ½æ ˆæº¢å‡º
*/
public class Codec {
// 这里的分隔符是有讲究的，如果æ¢æˆ'.'则在split的时候è¦è½¬ä¹‰ï¼Œä½†æ˜¯','ä¸ç”¨
private static final String SEP = ",";
// 这个尽å¯èƒ½çŸï¼ŒèŠ‚çœç©ºé—´
private static final String NULL = "X";
/** 递归版的 */
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root != null) {
sb.append(root.val).append(SEP);
sb.append(serialize(root.left)).append(SEP);
sb.append(serialize(root.right));
} else {
sb.append(NULL);
}
return sb.toString();
}
public TreeNode deserialize(String data) {
String[] texts = data.split(SEP);
Queue queue = new LinkedList(Arrays.asList(texts));
return helper(queue);
}
private TreeNode helper(Queue queue) {
if (queue.isEmpty()) {
return null;
}
String text = queue.poll();
if (text.equals(NULL)) {
return null;
}
int val = Integer.valueOf(text);
TreeNode root = new TreeNode(val);
root.left = helper(queue);
root.right = helper(queue);
return root;
}
/** 下é¢æ˜¯éžé€’归版的，å‰åºé历 */
public String serialize2(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root == null) {
sb.append(NULL);
return sb.toString();
}
Stack stack = new Stack();
while (!stack.isEmpty() || root != null) {
if (root != null) {
sb.append(root.val);
stack.push(root);
root = root.left;
} else {
sb.append(NULL);
root = stack.pop().right;
}
sb.append(SEP);
}
return sb.toString();
}
/**
* å‰åºè®¿é—®ä¸€é所有结点
* 在设置node时，从queueä¸å–出值
*/
public TreeNode deserialize2(String data) {
String[] texts = data.split(SEP);
Queue queue = new LinkedList(Arrays.asList(texts));
Deque stack = new LinkedList<>();
TreeNode root = getNode(queue), node = root;
while (!stack.isEmpty() || node != null) {
if (node != null) {
stack.push(node);
node.left = getNode(queue);
node = node.left;
} else {
node = stack.pop();
node.right = getNode(queue);
node = node.right;
}
}
return root;
}
private TreeNode getNode(Queue queue) {
if (queue.isEmpty()) {
return null;
}
String text = queue.poll();
if (text.equals(NULL)) {
return null;
}
return new TreeNode(Integer.parseInt(text));
}
/**
* BFS版的
*/
public String serialize3(TreeNode root) {
Queue queue = new LinkedList();
StringBuilder sb = new StringBuilder();
if (root == null) {
sb.append(NULL);
return sb.toString();
}
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
sb.append(NULL).append(SEP);
continue;
}
sb.append(node.val).append(SEP);
queue.add(node.left);
queue.add(node.right);
}
return sb.toString();
}
public TreeNode deserialize3(String data) {
String[] text = data.split(SEP);
Queue queue = new LinkedList(Arrays.asList(text));
Queue queue2 = new LinkedList();
TreeNode root = getNode(queue);
queue2.add(root);
while (!queue2.isEmpty()) {
TreeNode node = queue2.poll();
if (node == null) {
continue;
}
node.left = getNode(queue);
queue2.add(node.left);
node.right = getNode(queue);
queue2.add(node.right);
}
return root;
}
}