已知前序遍歷為{1,2,4,7,3,5,6,8}哼凯，中序遍歷為{4,7,2,1,5,3,8,6}斧蜕，它的二叉樹是怎么樣的部默？
二叉樹的前序遍歷遞歸算法：
public void preOrderTraverse(BiTree t) {
if (t == null) {
return;
}
System.out.print(t.val);
preOrderTraverse(t.left);
preOrderTraverse(t.right);
}
二叉樹的中序遍歷遞歸算法：
public void preOrderTraverse(BiTree t) {
if (t == null) {
return;
}
preOrderTraverse(t.left);
System.out.print(t.val);
preOrderTraverse(t.right);
}
二叉樹的后續(xù)遍歷遞歸算法：
public void preOrderTraverse(BiTree t) {
if (t == null) {
return;
}
preOrderTraverse(t.left);
preOrderTraverse(t.right);
System.out.print(t.val);
}
前序遍歷是先打印當(dāng)前節(jié)點(diǎn)再遞歸左和右份企，且前序遍歷的第一個(gè)節(jié)點(diǎn)的值為1甸鸟，所以1是根節(jié)點(diǎn)。
再由中序遍歷可知趟脂，2泰讽、4、7是1的左子樹的節(jié)點(diǎn)昔期，5菇绵、3、6镇眷、8是1的右子樹的節(jié)點(diǎn)。
image.png
然后看前序{2翎嫡、4欠动、7}可知4一定是2的子節(jié)點(diǎn)，而7有可能是2的子節(jié)點(diǎn)或4的子節(jié)點(diǎn)惑申。
看中序{4具伍、7、2}可知4是2的左子節(jié)點(diǎn)圈驼，7不可能是2的子節(jié)點(diǎn)（如果是的話中序應(yīng)該為{4人芽、2、7}或{7绩脆、2萤厅、4}）橄抹，所以結(jié)合前序可知7是4的子節(jié)點(diǎn)，且7是4的右子節(jié)點(diǎn)惕味。
image.png
同理推得：
image.png
參考自：《大話數(shù)據(jù)結(jié)構(gòu)》
