总结：
重建二叉树：其实就是根据前序和中序重建得到二叉树，得到后续，只要输出那边设置输出顺序即可
[编程题]重建二叉树 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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); } }输出：
74258631
转载于:https://www.cnblogs.com/snowwhite/p/4746374.html
