/**
* 给出一棵树的前序遍历和中序遍历,请构造这颗二叉树
* 注意:
* 可以假设树中不存在重复的节点
*/
/** * 给出一棵树的前序遍历和中序遍历,请构造这颗二叉树 * 注意: * 可以假设树中不存在重复的节点 */ public class Main55 { public static void main(String[] args) { int[] preorde = {1,2,4,5,3,6,7}; int[] inorder = {4,2,5,1,6,3,7}; System.out.println(Main55.buildTree(preorde, inorder)); } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder==null||inorder==null||preorder.length!=inorder.length) return null; return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1); } public static TreeNode build(int[] preorder, int[] inorder, int prestart, int preend, int instart, int inend){ // System.out.println("prestart = " + prestart + " preend = " + preend + " instart = " + instart + " inend = " + inend); if(preend<prestart||inend<instart) return null; TreeNode root= new TreeNode(preorder[prestart]); //System.out.println("root.val = " + root.val); int size = 0; int i = instart; for(; i <= inend; i++){ if(root.val == inorder[i]){ size = i - instart; break;} } root.left = build(preorder, inorder, prestart + 1, prestart + size, instart, i - 1 ); root.right = build(preorder, inorder, prestart + size + 1, preend , i + 1 ,inend ); return root; } }