我今天去接受采访,要求我序列化一棵二叉树.我实现了一种基于数组的方法,其中节点i的子节点(在水平顺序遍历中编号)处于左子节点的2*i索引和右子节点的2*i + 1.面试官似乎或多或少都很高兴,但我想知道序列化究竟意味着什么？它是否专门用于展平树以写入磁盘,或者序列化树还包括将树转换为链表,比方说.另外,我们如何将树扁平化为(双重)链表,然后重构它？您可以从链表重新创建树的确切结构吗？
我正在努力解决这个问题:http://uva.onlinejudge.org/external/7/732.html.对于给定的示例,它们给我们原始单词,例如TRIT和目标"anagramed"字符串TIRT.
目标:我们必须输出所有有效的'i'和'o'序列(分别是push和pop),它们从源字符串中产生目标字符串.
所以,我正在考虑计算"i"和"o"的所有排列,但是要减少这种情况:
1)如果当前排列以'o'开始,则停止检查,因为所有下一个排列都将以此pop命令开始,并且从空堆栈中弹出一些东西是无效的命令.
2)如果在检查过程中发现'o'命令并且堆栈中没有任何内容,则跳过该情况.
3)如果找到'i'命令并且输入字符串中没有任何内容,则跳过该情况.
4)如果找到'o'命令并且当前预期的字符不是刚刚弹出的字符,则跳过该情况,因为这将永远不会到达目标字符串.
5)不要搜索输入和目标字符串是否有不同的长度.
但我认为无论如何它可能会让我TLE ......
我知道这个理论:也许是一种排列并且一直在回溯.我实施它有太多困难.
有谁可以请与我分享一些代码或想法吗？
PS:当然,欢迎任何可能减少执行时间的建议.
存在具有特殊属性的二叉树,其所有内部节点具有val ='N'并且所有叶具有val ='L'.鉴于其预订.构造树并返回根节点.
每个节点可以有两个孩子或没有孩子