题目描述 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 解题思路 在二叉树的前序遍历中，第一个数字总是数的根结点的值，但在中序遍历中，根节点的值在序列的中间，左子树的节点的值位于根节点的转变，有右子树的值在根节点的右边，所以这道题可以使用递归的方式写代码
public class TreeNode { TreeNode left; TreeNode right; int data; public TreeNode(int data) { this.data = data; } } public class NewTreeNode { public TreeNode reConstructBinaryTree(int[] pre, int[] in) { TreeNode root = new TreeNode(pre[0]); int len = pre.length; if (len == 1) { root.left = null; root.right = null; return root; } int rootdata = root.data; int i; for (i = 0; i < len; i++) { if (rootdata == in[i]) { break; } } // 构建左子树 if (i > 0) { int[] newpre = new int[i]; int[] newio = new int[i]; for (int j = 0; j < i; j++) { newpre[j] = newpre[j + 1]; newio[j] = newio[j]; } root.left = reConstructBinaryTree(newpre, newio); } else { root.left = null; } // 构建右子树 if (len - i - 1 > 0) { int[] newpre = new int[len - i - 1]; int[] newio = new int[len - i - 1]; for (int j = i + 1; j < len; j++) { newio[j - i - 1] = in[j]; newpre[j - i - 1] = pre[j]; } root.right = reConstructBinaryTree(newpre, newio); } else { root.right = null; } return root; } }