algorithm - 从前序和后序遍历构建树

Question

如果我有前序和后序遍历，我是否可以构造一棵不一定是二叉树的树？像这样的东西:

预购:KLMOPN

后序:LOPMNK

构建:

   K
 / | \
L  M  N
  / \
 O   P

我读到，如果不对二叉树进行中序遍历，这是不可能的，但是对于非二叉树，是否可以仅使用前序遍历和后序遍历来做到这一点？

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)。

是它发生的顺序。