s*****p
发帖数: 26 | 1 昨天刚电面的G家，给一个binary tree(不是binary search tree, 也不一定
balanced).
要求efficiently store it in other data structure on disk, and reconstruct
the binary tree from this data structure.
自己没有做好，各位大神能给点解答么？ |
r**h
发帖数: 1288 | |
s*********t
发帖数: 52 | 3 inorder一遍，再postorder一遍，然后再恢复，行不 |
z*******o
发帖数: 4773 | 4 二叉树序列化够了,
瞎折腾啥? 还的存两倍的数据量.
【在 s*********t 的大作中提到】
: inorder一遍，再postorder一遍，然后再恢复，行不
|
p*****3
发帖数: 488 | 5 value,left offset,right offset
offset为0代表null, serialize和unserialize都是inorder |
g**G
发帖数: 767 | 6 这个题，leetcode的二叉树的题通刷了之后应该会做的吧，因为你总归要吧test case
copy到本机调试的
就是按level存即可
【在 s*****p 的大作中提到】
: 昨天刚电面的G家，给一个binary tree(不是binary search tree, 也不一定
: balanced).
: 要求efficiently store it in other data structure on disk, and reconstruct
: the binary tree from this data structure.
: 自己没有做好，各位大神能给点解答么？
|
c********p
发帖数: 1969 | |
s*****p
发帖数: 26 | 8
对，就一题
【在 c********p 的大作中提到】
: 让我先mark一下。。。
: 就问了一个题？
|
s*****p
发帖数: 26 | |
h*****n
发帖数: 15 | 10 序列化不是好解 因为对于不balance的树 空间复杂是2^n次，链表的话
个人觉得inorder+postorder 才是比较好的解 O（2n）还是线性解 |
|
|
r**h
发帖数: 1288 | 11 序列化空间都是2n啊，因为空节点数比树的节点数多1
序列化我觉得最大的好处是容易实现
【在 h*****n 的大作中提到】
: 序列化不是好解 因为对于不balance的树 空间复杂是2^n次，链表的话
: 个人觉得inorder+postorder 才是比较好的解 O（2n）还是线性解
|
p*****3
发帖数: 488 | 12 我觉得inorder+postorder的解法很差，一个是多用空间，一个是如果节点值一样的情
况树的形状有歧义。
leetcode的解法(用#标注空指针的那个)也不好，如果#可以是value的一部分呢 |
s*********s
发帖数: 318 | 13 这个有好的答案吗？leetcode的效率不说，连readNextToken()的实现都没有。 |
h*****n
发帖数: 15 | 14 序列化 不是应该2^n 么？ 如果 是一个极不平衡的树 ，每个节点只有右儿子
如果一般树的话，postorder 和 inorder 确实有问题，
以前看过这道题目，这里有个链接，这个算法太复杂，感觉面试估计写不出。
http://codegolf.stackexchange.com/questions/339/binary-tree-enc
我的想法是encode成一个数组
[num of node in cur level][node content][if node have children]...
5
/
3 2
/
2 1
/
9 9
[if node have children] 有4个状态 0 是没有child， 1是left only，2是2个，3是
right only
举个例子，
[1, 5, 2, //第一层，2 是表示 5这个node 有两个children， 1是这一层只有1个node
2， 3， 0， 2， 2， //第二层
2， 2， 2， 1， 0, //第三层
2, 9, 0, 9, 0]
这样整个空间是O(2n + logn)
不知道这样有没有问题？
【在 r**h 的大作中提到】
: 序列化空间都是2n啊，因为空节点数比树的节点数多1
: 序列化我觉得最大的好处是容易实现
|
E*******0
发帖数: 465 | 15 用#把树添成一个满树，比较好空间，但算法复杂度大大降低
1 1
/ /
2 3 2 3
/ / /
4 5 => # # 4 #
/ # # # # 7 # # #
7 # # # # ## ## #8 ######
\
8 |
x*****0
发帖数: 452 | |
g*******s
发帖数: 2963 | 17 leetcode test case里那种表达方式就行吧？ |
c********p
发帖数: 1969 | |
