1

鉴于具有独特元素的非二叉树的前序和后序遍历，我如何创建它们来自的树？

例如

给定预购 = ABCDEF
和后购 = BCEFDA

它应该构建一棵树，相当于
~~A~~~~~
~/~|~\~~~
B~C~D~~
~~~~/~\~~ ~
E~~F~

（对不起波浪号，这是我能弄清楚如何让树看起来正确并且仍然清晰的唯一方法）

无论如何，我不是要求代码来执行此操作，因为它是一个家庭作业项目，并且代码本身不是问题。我需要帮助的是比较两个输入的算法，以便它们可靠地创建正确的树

PS 给定的树可能或多或少具有任意数量（大概 <= 26）的节点

TL;博士
How do I use Pre-order and Post-order traversals to construct their original tree

4

1 回答 1

0

递归+迭代解决方案

每个级别处理传递给它的整个字符串

  • 如果第一个元素相等 - 删除并添加为当前级别的子级
  • 如果第一个元素不相等 - 删除第一个元素前序作为父元素并递归调用该子字符串到找到后序元素的位置

以空前哨作为 A 的父级调用

在大多数情况下，这将为您提供结果。

于 2014-02-21T05:57:31.833 回答