从先序遍历和后序遍历构建树

Question

如果我有前序遍历和后序遍历，我能构建出一棵不一定是二叉树的树吗？例如：

前序遍历：KLMOPN

后序遍历：LOPMNK

构建：

   K
 / | \
L  M  N
  / \
 O   P

我读到过，在二叉树中，只有通过中序遍历才能实现此操作，但是在非二叉树中，是否可以仅使用先序和后序遍历来完成呢？

- user1546716

---

假设后序遍历中的 Q 实际上应该是 O？另外，O 和 P 它们分别是从哪个字母分支出来的？是全部三个字母还是特定的一个字母？ - Lain

可能是从先序遍历和后序遍历列表重建树的重复问题。 - Bernhard Barker

Answer 1

如果树是用节点表示的（假设它是一个有3个节点的树，分别为左、中、右），则需要编写递归函数。

Void Transverse(Node n){
if( n.left ==null && n.middle==null && n.right ==null){
 System.out.print(n.value);
 return;

}
Transverse(left);
Transverse(middle);
Transverse(right);
System.out.print(n.value);

}

这是一些伪代码（我假设OP来自M），它将从您展示的树中打印出LOPMNK。

k->L（打印L）->k->M->O（打印O）->M->P（打印P）->M（打印M）->k->N（打印N）->k（打印k）。

这是它将发生的顺序。

- Lain