如何从给定的遍历中找到二叉树？

Question

如何从给定的遍历方法（inorder，post-order或pre-order）中找到二叉树？

Answer 1

维基百科的文章中序，后序，前序遍历树是在这里：

http://en.wikipedia.org/wiki/Tree_traversal。

您正在查找的树开始于与您的搜索词匹配的节点。

Answer 2

如果你想使用遍历结果恢复原始树，那么我对你有一些坏消息 - 没有明确的解决方案。将会有几棵树可以产生相同的遍历结果。

例如，对于序遍历以下的树木会产生相同的结果：1, 2, 3

2   3  1 
/\  /  \ 
    1 3  2   2 
      /   \ 
      1    3 

Answer 3

无法通过它只有一个遍历（中序，预购或后序）做到这一点。

这是可以做到。如果一棵树的中序&序遍历给出：

1. 序的第一个元素将是树的根。 （假设它是A）
2. Inorder中的Searc root所以所有左边的节点都是左子树的Inorder和右子树的Inorder。计算根节点左侧的节点数量L.
3. 从第二个节点的后序将是左子树的前序，之后是右子树的前序。

因此，我们找到了根元素，并将我们的Inorder排序到左子树的Inorder，右子树的Inorder和Pre子到左子树的预定义以及右子树的预序中。所以我们可以通过递归来做到这一点，直到只剩下一个节点。

同样，我们可以为Inorder和Postorder进行操作，其中root将是后单的最后一个元素。

Answer 4

（好吧，既然我们已经决定，amended question应该在这里，张贴我的答案也一样）

二叉树的后序和中序遍历给出below.Is有可能获得来自这些遍历的唯一二叉树？

这是可能的。

在后序遍历（左右根）中，整棵树的根节点总是最后一个（在你的情况下它是A）。在遍历（左 - 右）中，根之前的节点属于左子树，根之后的节点 - 右边的节点。由于我们已经确定了根，所以我们可以确定左子树和右子树中的节点。

确定后，我们可以在后序列表中分开左右子树。所以，现在我们已经确定了左右子树和根节点：

postorder: left|right|root 
inorder : left|root|right 

现在我们只需要递归构造左右子树。鳍。