定義節(jié)點(diǎn)類型
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
重構(gòu)二叉樹(shù)
public class ReconstructBinaryTree {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0,
in.length - 1);
}
public TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre,
int[] in, int startIn, int endIn) {
if (startPre > endPre || startIn > endIn)
return null;
TreeNode root = new TreeNode(pre[startPre]);// 構(gòu)造樹(shù)根
for (int i = startIn; i <= endIn; i++) {
// 中序遍歷中找樹(shù)根
if (in[i] == pre[startPre]) {
root.left = reConstructBinaryTree(pre, startPre + 1, i
- startIn + startPre, in, startIn, i - 1);
root.right = reConstructBinaryTree(pre, i - startIn + startPre
+ 1, endPre, in, i + 1, endIn);
break;
}
}
return root;
}
}
測(cè)試
public class Test {
public static void main(String[] args) {
new ReconstructBinaryTree().reConstructBinaryTree(new int[] { 1, 2, 4,
7, 3, 5, 6, 8 }, new int[] { 4, 7, 2, 1, 5, 3, 8, 6 });
}
}
分析
前序遍歷：12473568
中序遍歷：47215386
重構(gòu)過(guò)程：
- 前序遍歷中的第一個(gè)值為樹(shù)根
- 樹(shù)根在中序遍歷中的位置把鉴，左側(cè)為左子樹(shù)的中序遍歷結(jié)果（472）故响，右側(cè)為右子樹(shù)的中序遍歷結(jié)果（5386）
- 在前序遍歷中，左子樹(shù)的前序遍歷結(jié)果為（247）肯污，右子樹(shù)的前序遍歷結(jié)果為（3568）
- 則2為左子樹(shù)的樹(shù)根翘单，3為右子樹(shù)的樹(shù)根
- 重復(fù)上述操作直至結(jié)束
