原文地址：Construct Tree from given Inorder and Preorder traversals
我们考虑下下面的遍历：
中序遍历：D B E A F C 先序遍历：A B D E C F
在一个先序序列中，最左端的元素就是树根。所以我们知道A是已知序列的根。通过查询A的中序序列，我们可以得到A左边左子树的所有元素和右边右子树的所有元素。所以我们现在知道了以下结构。
A / \ / \ D B E F C我们递归上述步骤，然后得到下面的树：
A / \ / \ B C / \ / / \ / D E F算法： buildTree()
1）从先序序列中选一个元素。增加一个先序索引变量（下面代码中的preIndex）来选择下一次递归调用的下一个元素。 2）用已选择的元素的值创建一个新的树节点tNode。 3）找到已选择元素在中序遍历中的索引。设这个索引为inIndex。 4）在inIndex之前调用buildTree，建立树作为tNode的左子树。 5）在inIndex之后调用buildTree，建立树作为tNode的右子树。 6）返回tNode。
// Java program to construct a tree using inorder and preorder traversal /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { char data; Node left, right; Node(char item) { data = item; left = right = null; } } class BinaryTree { Node root; static int preIndex = 0; /* Recursive function to construct binary of size len from Inorder traversal in[] and Preorder traversal pre[]. Initial values of inStrt and inEnd should be 0 and len -1. The function doesn't do any error checking for cases where inorder and preorder do not form a tree */ Node buildTree(char in[], char pre[], int inStrt, int inEnd) { if (inStrt > inEnd) return null; /* Pick current node from Preorder traversal using preIndex and increment preIndex */ Node tNode = new Node(pre[preIndex++]); /* If this node has no children then return */ if (inStrt == inEnd) return tNode; /* Else find the index of this node in Inorder traversal */ int inIndex = search(in, inStrt, inEnd, tNode.data); /* Using index in Inorder traversal, construct left and right subtress */ tNode.left = buildTree(in, pre, inStrt, inIndex - 1); tNode.right = buildTree(in, pre, inIndex + 1, inEnd); return tNode; } /* UTILITY FUNCTIONS */ /* Function to find index of value in arr[start...end] The function assumes that value is present in in[] */ int search(char arr[], int strt, int end, char value) { int i; for (i = strt; i <= end; i++) { if (arr[i] == value) return i; } return i; } /* This funtcion is here just to test buildTree() */ void printInorder(Node node) { if (node == null) return; /* first recur on left child */ printInorder(node.left); /* then print the data of node */ System.out.print(node.data + " "); /* now recur on right child */ printInorder(node.right); } // driver program to test above functions public static void main(String args[]) { BinaryTree tree = new BinaryTree(); char in[] = new char[]{'D', 'B', 'E', 'A', 'F', 'C'}; char pre[] = new char[]{'A', 'B', 'D', 'E', 'C', 'F'}; int len = in.length; Node root = tree.buildTree(in, pre, 0, len - 1); // building the tree by printing inorder traversal System.out.println("Inorder traversal of constructed tree is : "); tree.printInorder(root); } } // This code has been contributed by Mayank Jaiswal输出：
Inorder traversal of constructed tree is : D B E A F C时间复杂度： O(n2) ，当树是一个左退化树的时候，发生最坏的情况。例如先序遍历与中序遍历最坏的情况是 {A, B, C, D}与{D, C, B, A}。
