https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
本以为需要将 Tree 变成 preorder/postorder + inorder,然后再construct from the two strings. 题解只用了一个String,其思路是 preorder 或者 level order,每个非 null 的node 都有对应的两个 node。
preorder/postorder + inorder 的思路,是不允许 duplicated values。而下面的题解,是允许的。
level order solution
public class Codec {
private final static String SPLITTER = ", ";
private final static String NULL_VALUE = "n";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder builder = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
builder.append(NULL_VALUE).append(SPLITTER);
} else {
queue.offer(node.left);
queue.offer(node.right);
builder.append(node.val).append(SPLITTER);
}
}
return builder.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.startsWith(NULL_VALUE)) {
return null;
}
String[] values = data.split(SPLITTER);
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(values[0]));
queue.offer(root);
for (int i = 1; i < values.length; i++) {
TreeNode node = queue.poll();
if (!values[i].equals(NULL_VALUE)) {
node.left = new TreeNode(Integer.parseInt(values[i]));
queue.offer(node.left);
}
i++;
if (!values[i].equals(NULL_VALUE)) {
node.right = new TreeNode(Integer.parseInt(values[i]));
queue.offer(node.right);
}
}
return root;
}
}
preorder solution
from: https://www.jianshu.com/p/4c2a929c31c3
private static final String spliter = ",";
private static final String NN = "X";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preorder(root, sb);
return sb.toString();
}
private void preorder(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NN).append(spliter);
return;
}
sb.append(node.val).append(spliter);
preorder(node.left, sb);
preorder(node.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList<>();
queue.addAll(Arrays.asList(data.split(spliter)));
//如何返回root:递归返回的最终就是root
return buildTree(queue);
}
private TreeNode buildTree(Queue<String> queue) {
String val = queue.poll();
if (val.equals(NN)) {
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(queue);
node.right = buildTree(queue);
return node;
}
顺便把 105. Construct Binary Tree from Preorder and Inorder Traversal 写了一遍:
需要琢磨的一点是,当前node 的 right child 在 preorder 中的寻找方式。举个例子很容易想明白,'inStart - inIndex' 为 left subtree 的 size,那么 'preStart + (inStart - inIndex) + 1' 即为 right subtree 的 root,亦即当前 node 的right child。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildHelper(0, 0, inorder.length - 1, preorder, inorder);
}
private TreeNode buildHelper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart >= preorder.length || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = findIndex(root.val, inStart, inEnd, inorder);
int leftSubTreeSize = inIndex - inStart;
root.left = buildHelper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
root.right = buildHelper(preStart + leftSubTreeSize + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
private int findIndex(int target, int start, int end, int[] array) {
for (int i = start; i <= end; i++) {
if (array[i] == target) {
return i;
}
}
return -1;
}
}
网友评论