如果我有前序和后序遍历,我是否可以构造一棵不一定是二叉树的树?像这样的东西:
预购:KLMOPN
后序:LOPMNK
构建:
K
/ | \
L M N
/ \
O P
我读到,如果不对二叉树进行中序遍历,这是不可能的,但是对于非二叉树,是否可以仅使用前序遍历和后序遍历来做到这一点?
最佳答案
如果树是在节点中完成的(假设它是一个 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)。
是它发生的顺序。
关于algorithm - 从前序和后序遍历构建树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21964309/