从前序和后序遍历构建树

Question

如果我有前序和后序遍历，我可以构建一个不一定是二叉树的树吗？类似的东西：

预购：KLMOPN

后订单：LOPMNK

构建：

   K
 / | \
L  M  N
  / \
 O   P

我已经读到，如果没有二叉树的顺序遍历，这是不可能的，但是对于非二叉树，有可能只使用前序和后序遍历吗？

Answer 1

如果树是在节点中完成的（假设它是一个三节点树，左、中、右）。您将编写一个递归函数。

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-

这是它发生的顺序。