原文地址：Construct a Binary Tree from Postorder and Inorder
已知后续与中序遍历，构建树。
例子：
Input : in[] = {2, 1, 3} post[] = {2, 3, 1} Output : Root of below tree 1 / \ 2 3 Input : in[] = {4, 8, 2, 5, 1, 6, 3, 7} post[] = {8, 4, 5, 2, 6, 7, 3, 1} Output : Root of below tree 1 / \ 2 3 / \ / \ 4 5 6 7 \ 8我们在前面已经讨论了用中序遍历和先序遍历构建二叉树。这个想法也是类似的。
我们看下用 in[] = {4, 8, 2, 5, 1, 6, 3, 7}与post[] = {8, 4, 5, 2, 6, 7, 3, 1}构建二叉树的过程。
1）首先找到post[]中的最后一个节点。最后一个节点是1，我们知道这个值是树根，因为树根总数出现在后续遍历的最后。 2）我们在in[]中查找1，找到根的左子树与右子树。在in[]中，1左边的全部都是左子树的节点，右边的全部都是右子树的节点。
1 / \ [4,8,2,5] [6,3,7]3）我们用两个步骤递归上面的过程：
递归in[] = {6,3,7}与post[] = {6,7,3}。建立树并作为根的右子树。递归in[] = {4,8,2,5}与post[] = {8,4,5,2}。建立树并作为根的左子树。下面是上述思想的Java代码实现。一个十分重要的发现，我们先递归右子树先于左子树，这是因为无论在什么时候建立一个新的节点，我们都减少了后序的索引。
// Java program to construct a tree using inorder // and postorder traversals /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { int data; Node left, right; public Node(int data) { this.data = data; left = right = null; } } // Class Index created to implement pass by reference of Index class Index { int index; } class BinaryTree { /* Recursive function to construct binary of size n from Inorder traversal in[] and Preorder traversal post[]. Initial values of inStrt and inEnd should be 0 and n -1. The function doesn't do any error checking for cases where inorder and postorder do not form a tree */ Node buildUtil(int in[], int post[], int inStrt, int inEnd, Index pIndex) { // Base case if (inStrt > inEnd) return null; /* Pick current node from Preorder traversal using postIndex and decrement postIndex */ Node node = new Node(post[pIndex.index]); (pIndex.index)--; /* If this node has no children then return */ if (inStrt == inEnd) return node; /* Else find the index of this node in Inorder traversal */ int iIndex = search(in, inStrt, inEnd, node.data); /* Using index in Inorder traversal, construct left and right subtress */ node.right = buildUtil(in, post, iIndex + 1, inEnd, pIndex); node.left = buildUtil(in, post, inStrt, iIndex - 1, pIndex); return node; } // This function mainly initializes index of root // and calls buildUtil() Node buildTree(int in[], int post[], int n) { Index pIndex = new Index(); pIndex.index = n - 1; return buildUtil(in, post, 0, n - 1, pIndex); } /* Function to find index of value in arr[start...end] The function assumes that value is postsent in in[] */ int search(int arr[], int strt, int end, int value) { int i; for (i = strt; i <= end; i++) { if (arr[i] == value) break; } return i; } /* This funtcion is here just to test */ void preOrder(Node node) { if (node == null) return; System.out.print(node.data + " "); preOrder(node.left); preOrder(node.right); } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int in[] = new int[]{4, 8, 2, 5, 1, 6, 3, 7}; int post[] = new int[]{8, 4, 5, 2, 6, 7, 3, 1}; int n = in.length; Node root = tree.buildTree(in, post, n); System.out.println("Preorder of the constructed tree : "); tree.preOrder(root); } } // This code has been contributed by Mayank Jaiswal(mayank_24)输出：
Preorder of the constructed tree : 1 2 4 8 5 3 6 7时间复杂度： O(n2)
