算法
BFS遍历二叉树
serialize时间复杂度: O(n)
serialize空间复杂度: O(n)
deserialize时间复杂度: O(n)
deserialize空间复杂度: O(n)
serialize中FORMAT: 0:LeetCode格式; 1:AcWing格式
deserialize兼容LeetCode格式和AcWing格式
C++代码
class Codec {
public:
static string serialize(TreeNode *root) {
const int FORMAT = 0; // 0:LeetCode; 1:AcWing
string res("[");
queue<TreeNode *> queue0;
queue0.push(root);
while (!queue0.empty()) {
const int levelSize = static_cast<int>(queue0.size());
const int resSize = static_cast<int>(res.size());
int cnt = 0;
for (int i = 0; i < levelSize; ++i) {
TreeNode *node = queue0.front();
queue0.pop();
if (!node) {
res += "null,";
continue;
}
res += to_string(node->val);
res.push_back(',');
++cnt;
queue0.push(node->left);
queue0.push(node->right);
}
if (!cnt && FORMAT == 0) {
res.resize(resSize);
}
}
if (res.back() == ',') {
res.back() = ']';
} else {
res.push_back(']');
}
return res;
}
static TreeNode *deserialize(const string &data) {
if (data.size() <= 2 || data.front() != '[' || data.back() != ']') {
return NULL;
}
const int end = static_cast<int>(data.size()) - 1;
int index = 1;
TreeNode *const root = deserialize(data, index, end);
if (index >= end) {
return root;
}
queue<TreeNode *> queue0;
queue0.push(root);
while (!queue0.empty()) {
const int levelSize = static_cast<int>(queue0.size());
for (int i = 0; i < levelSize; ++i) {
TreeNode *node = queue0.front();
queue0.pop();
if (!node) {
continue;
}
node->left = deserialize(data, index, end);
if (index >= end) {
break;
}
queue0.push(node->left);
node->right = deserialize(data, index, end);
if (index >= end) {
break;
}
queue0.push(node->right);
}
}
return root;
}
private:
static TreeNode *deserialize(const string &data, int &index, int end) {
for (; index < end && isspace(data[index]); ++index) {
}
if (index >= end) {
return NULL;
}
TreeNode *node = NULL;
if (isdigit(data[index]) || data[index] == '+' || data[index] == '-') {
const int val = atoi(&data[index]);
node = new TreeNode(val);
}
for (; index < end && data[index] != ','; ++index) {
}
++index;
return node;
}
};
Java代码
public class Codec {
public static String serialize(final TreeNode root) {
final int FORMAT = 0; // 0:LeetCode, 1:AcWing
final StringBuilder res = new StringBuilder();
res.append('[');
final Queue<TreeNode> queue0 = new LinkedList<>();
queue0.add(root);
while (!queue0.isEmpty()) {
final int levelSize = queue0.size();
final int resSize = res.length();
int cnt = 0;
for (int i = 0; i < levelSize; ++i) {
TreeNode node = queue0.poll();
if (node == null) {
res.append("null,");
continue;
}
res.append(node.val);
res.append(',');
++cnt;
queue0.add(node.left);
queue0.add(node.right);
}
if (cnt == 0 && FORMAT == 0) {
res.setLength(resSize);
}
}
if (res.charAt(res.length() - 1) == ',') {
res.setCharAt(res.length() - 1, ']');
} else {
res.append(']');
}
return res.toString();
}
public static TreeNode deserialize(final String data) {
if (data.length() <= 2 || data.charAt(0) != '[' || data.charAt(data.length() - 1) != ']') {
return null;
}
final int end = data.length() - 1;
final int[] indexArr = {1};
final TreeNode root = deserialize1(data, indexArr, end);
if (indexArr[0] >= end) {
return root;
}
final Queue<TreeNode> queue0 = new LinkedList<>();
queue0.add(root);
while (!queue0.isEmpty()) {
final int levelSize = queue0.size();
for (int i = 0; i < levelSize; ++i) {
final TreeNode node = queue0.poll();
if (node == null) {
continue;
}
node.left = deserialize1(data, indexArr, end);
if (indexArr[0] >= end) {
break;
}
node.right = deserialize1(data, indexArr, end);
if (indexArr[0] >= end) {
break;
}
queue0.add(node.left);
queue0.add(node.right);
}
}
return root;
}
private static TreeNode deserialize1(final String data, final int[] indexArr, final int end) {
int index = indexArr[0];
for (; index < end && Character.isSpaceChar(data.charAt(index)); ++index) {
}
if (index >= end) {
indexArr[0] = index;
return null;
}
TreeNode node = null;
final char ch = data.charAt(index);
if (Character.isDigit(ch) || ch == '+' || ch == '-') {
final int start = index;
for (; index < end && data.charAt(index) != ','; ++index) {
}
final String strVal = data.substring(start, index);
final int val = Integer.parseInt(strVal);
node = new TreeNode(val);
}
for (; index < end && data.charAt(index) != ','; ++index) {
}
++index;
indexArr[0] = index;
return node;
}
}
Python3代码
太强了