定义节点类型
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
重构二叉树
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]);// 构造树根
for (int i = startIn; i <= endIn; i++) {
// 中序遍历中找树根
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;
}
}
测试
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
重构过程：
- 前序遍历中的第一个值为树根
- 树根在中序遍历中的位置，左侧为左子树的中序遍历结果（472），右侧为右子树的中序遍历结果（5386）
- 在前序遍历中，左子树的前序遍历结果为（247），右子树的前序遍历结果为（3568）
- 则2为左子树的树根，3为右子树的树根
- 重复上述操作直至结束
