0

考虑我想以序列化方式传输二叉树，我只有一个字符串来传递该树，我只能使用一次遍历的帮助，有什么办法可以做到吗？- （在 Ebay 上被问到）..

换句话说，可以只使用一个树遍历字符串来生成二叉树吗？面试官还给了我一个提示，说我可以在没有叶子的地方使用 null ..

4

3 回答 3

2

http://www.seas.gwu.edu/~csci133/fall05/trees-fig4.jpg

请考虑上图中的树，如果我们只想使用 1 次遍历传递一个字符串，我们可以在该特定位置没有子节点时放置特殊符号。

现在如果我们通过 1 2 4 7 $ $ $ 5 $ $ 3 $ 6 8 $ $ 9 $ $

                                        1
                                     /      \
                                   2        3
                                  /  \     / \
                                 4    5   $   6
                                / \  / \     / \
                               7   $ $  $    8   9
                              / \           /\  /\
                             $  $          $ $ $ $

这里 $ 意味着孩子是空的，所以移动到订单的下一个位置。

如果我错了，请纠正我，以上是不可能的......

于 2013-01-28T07:34:42.777 回答
2

[编辑] 鉴于这似乎是一些给定的任务，而不是真正的现实问题，答案没有意义。第二次尝试：

看到您可以使用空值，您确实可以使用带有空值的预购。

a b null null c null null将是一棵看起来像的树(a (b) (c))，而(a (b (c)) )将被编码为a b c null null null null（请注意，我给每个叶子两个空子节点，也许没有它也可以工作）

于 2013-01-28T07:21:38.760 回答
0

如果您想用字符串、字节 [] 或流表示任何对象，您可以查看 JSON 序列化或 XML 序列化。

于 2013-01-28T07:10:28.897 回答