总结：
重建二叉树：其实就是根据前序和中序重建得到二叉树，得到后续，只要输出那边设置输出顺序即可
[编程题]重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
完整通过代码：
先新建一个二叉树的类
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
再
public class reConstructBinaryTree {
public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre==null||in==null){ return null; }
TreeNode tree = reConstructCore(pre,in,0,pre.length-1,0,in.length-1);
return tree;
}
/**
*核心算法，preStart和preEnd是起始下标和结束下标
**/
public static TreeNode reConstructCore(int[] pre,int[] in,int preStart,int preEnd,int inStart,int inEnd){
TreeNode tree = new TreeNode(pre[preStart]);
tree.left = null;
tree.right= null;
if(preStart==preEnd&&inStart==inEnd){ return tree; }
//记录中序遍历中等于前序遍历的第一位的下标
int inCenter = 0;
for(inCenter = inStart;inCenter<inEnd;inCenter++){
if(in[inCenter]==pre[preStart]){
break;
}
}
//左子树的长度
int leftTreeLength = inCenter-inStart;
//右子数的长度
int rightTreeLength = inEnd-inCenter;
if(leftTreeLength>0){
tree.left = reConstructCore(pre,in,preStart+1,preStart+leftTreeLength,inStart,inCenter-1);
}
if(rightTreeLength>0){
tree.right = reConstructCore(pre,in,preStart+leftTreeLength+1,preEnd,inCenter+1,inEnd);
}
return tree;
}
public static void traverseBinTreeRDL(TreeNode node){
if (node==null) { return; }
if (node.left!=null) {
traverseBinTreeRDL(node.left); }
if(node.right!=null) {
traverseBinTreeRDL(node.right); }
System.out.println(node.val);
}
public static void main(String[] arg0){
int pre[]= {1,2,4,7,3,5,6,8};
int in[] = {4,7,2,1,5,3,8,6};
TreeNode tree = reConstructBinaryTree(pre, in);
traverseBinTreeRDL(tree);
}
}
输出：
7
4
2
5
8
6
3
1