题解 |JZ37 序列化二叉树
这道题的难点是在设计序列化和反序列化的结构上。
个人认为前序遍历好写一些。
有两点需要注意：
1.如果是空节点，需要标出来。我这里用的是'#'作为标记。搜索到这个标记，就不会再往下搜索。
2.在插入数字的时候，需要在插入完后做一个标记。否则上一个节点会和下一个节点的数字会造成处理混乱。比如上一个节点是123，下一个节点是456。放入序列化中是123456，不知道这六个数字哪一个是上一个节点，哪一个是下一个节点，所以需要做分割。我这里采用的是'@'作为数字之间的分割。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
string ans = "";
int pos;
char* Serialize(TreeNode *root) {
// string ans = "";
ans = "";
in_order(root);
char* str;
int len = ans.length();
str = (char*)malloc((len+1)*sizeof(char));
ans.copy(str, len, 0);
return str;
}
TreeNode* in_order(TreeNode* p) {
if (!p) {
ans += "#";
return nullptr;
}
ans += to_string(p->val);
ans += "@";
in_order(p->left);
in_order(p->right);
return p;
}
TreeNode* Deserialize(char *str) {
pos = 0;
TreeNode* root = un_order(str);
return root;
}
TreeNode* un_order(char* str) {
if (pos >= strlen(str)) {
return nullptr;
}
if (str[pos] == '#') {
pos++;
return nullptr;
}
TreeNode* root = new TreeNode(-1);
int num = get_number(str, pos);
root->val = num;
pos++;
root->left = un_order(str);
root->right = un_order(str);
return root;
}
int get_number(char* str, int &pos) {
int ans = 0;
while(str[pos] != '@') {
ans = ans * 10 + str[pos] - '0';
pos++;
}
return ans;
}
};
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
ans = []
pos = 0
def Serialize(self, root):
# write code here
self.in_order(root)
return self.ans
def in_order(self, root):
if not root:
self.ans.append('#')
return None
self.ans.append(str(root.val))
self.ans.append('@')
self.in_order(root.left)
self.in_order(root.right)
return "".join(self.ans)
def Deserialize(self, s):
# write code here
self.pos = 0
root = self.un_order(s)
return root
def un_order(self, s):
if self.pos >= len(s):
return None
if s[self.pos] == '#':
self.pos += 1
return None
num = self.get_number(s)
self.pos += 1
root = TreeNode(-1)
root.val = num
root.left = self.un_order(s)
root.right = self.un_order(s)
return root
def get_number(self, s):
ans = 0
while s[self.pos] != '@':
ans = ans * 10 + int(s[self.pos])
self.pos += 1
return ans
查看18道真题和解析
投递零跑科技等公司10个岗位 >
