本文共 3631 字，大约阅读时间需要 12 分钟。

原文地址：

已知后续与中序遍历，构建树。

例子：

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，我们知道这个值是树根，因为树根总数出现在后续遍历的最后。

1       /    \[4,8,2,5]   [6,3,7]

3）我们用两个步骤递归上面的过程：

1. 递归in[] = {6,3,7}与post[] = {6,7,3}。建立树并作为根的右子树。
2. 递归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 Indexclass 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(n^2)$

转载地址：http://rkhii.baihongyu.com/