e***s
发帖数: 799 | 1 再CAIWU的面经上看到的，有没有大牛给个IDEA？ |
j*****y
发帖数: 1071 | 2 感觉还是可以用 pre-order travers 一个 left child, right siblin 的结构吧.
【在 e***s 的大作中提到】
: 再CAIWU的面经上看到的，有没有大牛给个IDEA？
|
w****x
发帖数: 2483 | 3 /*
Serialize/DeSerialize a tree
*/
struct NODE
{
int nVal;
vector vec;
NODE(int n) : nVal(n) {}
};
void _inner_serial(NODE* pNode, char*& p)
{
if (NULL == pNode)
return;
*p++ = pNode->vec.size();
*p++ = pNode->nVal;
for (vector::iterator it = pNode->vec.begin();
it != pNode->vec.end(); it++)
_inner_serial(*it, p);
}
const char* Serialize(NODE* pRoot, char mem[])
{
if (NULL == mem || NULL == pRoot)
return NULL;
char* p = mem;
_inner_serial(pRoot, p);
return mem;
}
NODE* _inner_deserial(const char*& p)
{
int n = *p++;
NODE* pRet = new NODE(*p++);
for (int i = 0; i < n; i++)
pRet->vec.push_back(_inner_deserial(p));
return pRet;
}
NODE* DeSerialize(const char mem[])
{
if (NULL == mem)
return NULL;
const char* p = mem;
return _inner_deserial(p);
} |
j*****y
发帖数: 1071 | 4 thanks.
【在 w****x 的大作中提到】
: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)
|
j*****y
发帖数: 1071 | 5 这种情况下 child是没有顺序的，是吧？
如何把 serialized的 array写到一个file去，然后从file读回来 重建树呢？
多谢 :)
【在 w****x 的大作中提到】
: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)
|
c***w
发帖数: 134 | 6
我一直对你的头像很感兴趣，这个女的是谁？
【在 w****x 的大作中提到】
: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)
|
e***s
发帖数: 799 | 7 非常感谢！！
【在 w****x 的大作中提到】
: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)
|
e***s
发帖数: 799 | 8 再CAIWU的面经上看到的，有没有大牛给个IDEA？ |
j*****y
发帖数: 1071 | 9 感觉还是可以用 pre-order travers 一个 left child, right siblin 的结构吧.
【在 e***s 的大作中提到】
: 再CAIWU的面经上看到的，有没有大牛给个IDEA？
|
w****x
发帖数: 2483 | 10 /*
Serialize/DeSerialize a tree
*/
struct NODE
{
int nVal;
vector vec;
NODE(int n) : nVal(n) {}
};
void _inner_serial(NODE* pNode, char*& p)
{
if (NULL == pNode)
return;
*p++ = pNode->vec.size();
*p++ = pNode->nVal;
for (vector::iterator it = pNode->vec.begin();
it != pNode->vec.end(); it++)
_inner_serial(*it, p);
}
const char* Serialize(NODE* pRoot, char mem[])
{
if (NULL == mem || NULL == pRoot)
return NULL;
char* p = mem;
_inner_serial(pRoot, p);
return mem;
}
NODE* _inner_deserial(const char*& p)
{
int n = *p++;
NODE* pRet = new NODE(*p++);
for (int i = 0; i < n; i++)
pRet->vec.push_back(_inner_deserial(p));
return pRet;
}
NODE* DeSerialize(const char mem[])
{
if (NULL == mem)
return NULL;
const char* p = mem;
return _inner_deserial(p);
} |
|
|
j*****y
发帖数: 1071 | 11 thanks.
【在 w****x 的大作中提到】
: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)
|
j*****y
发帖数: 1071 | 12 这种情况下 child是没有顺序的，是吧？
如何把 serialized的 array写到一个file去，然后从file读回来 重建树呢？
多谢 :)
【在 w****x 的大作中提到】
: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)
|
c***w
发帖数: 134 | 13
我一直对你的头像很感兴趣，这个女的是谁？
【在 w****x 的大作中提到】
: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)
|
e***s
发帖数: 799 | 14 非常感谢！！
【在 w****x 的大作中提到】
: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)
|
u*****o
发帖数: 1224 | 15 是赵雅芝啊，好像是她在京华烟云里姚木兰的扮相。。
【在 c***w 的大作中提到】
:
: 我一直对你的头像很感兴趣，这个女的是谁？
|
S********t
发帖数: 3431 | 16 you can encode the structure of the generic tree with 2n bits, and
reconstruct the structure from the 2n bits
【在 e***s 的大作中提到】
: 再CAIWU的面经上看到的，有没有大牛给个IDEA？
|
m*****k
发帖数: 731 | 17 抛一砖：
How about in-order traversal?
String serialize(Node root){
if(root == null){
return "()";
}
else{
return "(" + serialize( root.left) + root.val + serialize( root.
right) + ")" ;
}
}
ex:
1
/ \
2 3
/ \
4 5
will return
( ( (()4()) 2 ( ()5()) ) 1 ( ()3 () ) )
deserialize:
easy with stack, |
z****e
发帖数: 54598 | 18 做一个bfs就好了
((root))
(()(1)(2))
(()(3)()(4)) |
