Question

二叉树，如何从两种遍历的结果推出另一种遍历？方法简单详细一点。注意不是编程求解

不要在百度找，因为百度的我已经看过了，看不懂。

Answer 1

递归求解，已知先序和中序，或者后序和中序都能求出一种唯一的。
例如
先序：ABCDE
中序：CBDAE
递归第一次：在所有节点中找根节点，即先序最左边的（A），所以（A）为根节点。
再到中序里以A为分界线分成左子树（CBD）和右子树（E）；
递归第二次：在左子树（CBD）中找根节点，及左子树节点中在先序里最靠前的（B），以（B）
分割，即左子树（C），右子树（D）；
递归结束条件：只有一个节点是返回。
还有什么不懂可以问我 ，后序是一样的。

Answer 2

已知前序中序求后序
procedure Solve(pre,mid:string);
var i:integer;
begin
if (pre='') or (mid='') then exit;
i:=pos(pre[1],mid);
solve(copy(pre,2,i),copy(mid,1,i-1));
solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i));
post:=post+pre[1];
end;
已知中序后序求前序（NOIP2001普及组第3题）
procedure Solve(mid,post:string);
var i:integer;
begin
if (mid='') or (post='') then exit;
i:=pos(post[length(post)],mid);
pre:=pre+post[length(post)];
solve(copy(mid,1,I-1),copy(post,1,I-1));
solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i));
end;
已知前序后序求中序
function ok(s1,s2:string):boolean;
var i,l:integer; p:boolean;
begin
ok:=true;
l:=length(s1);
for i:=1 to l do begin
p:=false;
for j:=1 to l do if s1[i]=s2[j] then p:=true;
if not p then begin ok:=false;exit;end;
end; end;
Procedure solve(pre,post:string);
var i:integer;
begin
if (pre='') or (post='') then exit;
i:=0;
repeat
inc(i);
until ok(copy(pre,2,i),copy(post,1,i));
solve(copy(pre,2,i),copy(post,1,i));
midstr:=midstr+pre[1];
solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1));
end;