给出二叉树的中序和后序遍历，构建出二叉树

我会带着你远行 2022-04-05 06:59 188阅读 0赞

假设二叉树中序遍历为：

> int\[\] inOrder = \{ 4, 2, 5, 1, 6, 3, 7 \};

后序遍历为

> int\[\] postOrder = \{ 4, 5, 2, 6, 7, 3, 1 \};

那么，如何构建还原出这颗二叉树？类似问题还有：给出二叉树的先序和中序遍历如何还原出二叉树

**算法思想：**

*  后序遍历中的最后一个元素为二叉树的根节点，这里是数字**1**
 *  在中序遍历集合中查找数字**1**，记作位置**i**，注意**i**的左边是左子树，右边是右子树
 *  假设在步骤2中，有**X**个元素在**i**的左侧，那么从后序遍历集合中取前**X**个元素，得到的结果子集合即为左子树的后序遍历，类似的，**i**的右侧有**Y**个元素，那么，从后续遍历集合中取接下来的**Y**个元素，得到的结果即为右子树的后序遍历
 *  通过步骤2和步骤3构建出根节点的左子树和右子树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thbmdrYW5nbG91_size_16_color_FFFFFF_t_70]

**算法实现：**

public class InorderPostOrderToTree {
    
        public static int pIndex = 0;
    
        public Node makeBTree(int[] inOrder, int[] postOrder, int iStart, int iEnd,
                              int postStart, int postEnd) {
            if (iStart > iEnd || postEnd > postEnd) {
                return null;
            }
    
            int rootValue = postOrder[postEnd];
            Node root = new Node(rootValue);
            pIndex++;
    
            if (iStart == iEnd) {
                return root;
            }
            int index = getInorderIndex(inOrder, iStart, iEnd, root.data);
            root.left = makeBTree(inOrder, postOrder, iStart, index - 1, postStart,
                    postStart + index - (iStart + 1));
            root.right = makeBTree(inOrder, postOrder, index + 1, iEnd, postStart
                    + index - iStart, postEnd - 1);
            return root;
        }
    
        public int getInorderIndex(int[] inOrder, int start, int end, int data) {
            for (int i = start; i <= end; i++) {
                if (inOrder[i] == data) {
                    return i;
                }
            }
            return -1;
        }
    
        public void printInorder(Node root) {
            if (root != null) {
                printInorder(root.left);
                System.out.print(root.data + " ");
                printInorder(root.right);
            }
        }
    
        public static void main(String[] args) {
            int[] inOrder = {4, 2, 5, 1, 6, 3, 7};
            int[] postOrder = {4, 5, 2, 6, 7, 3, 1};
            InorderPostOrderToTree i = new InorderPostOrderToTree();
            Node x = i.makeBTree(inOrder, postOrder, 0, inOrder.length - 1, 0,
                    postOrder.length - 1);
            System.out.println("inorder traversal of constructed tree:");
            i.printInorder(x);
    
        }
    }
    
    class Node {
        int data;
        Node left;
        Node right;
    
        public Node(int data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

**输出结果**

inorder traversal of constructed tree:
    4 2 5 1 6 3 7

[https://algorithms.tutorialhorizon.com/construct-a-binary-tree-from-given-inorder-and-postorder-traversal/][https_algorithms.tutorialhorizon.com_construct-a-binary-tree-from-given-inorder-and-postorder-traversal]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thbmdrYW5nbG91_size_16_color_FFFFFF_t_70]: /images/20220405/1d7f7935e12c4ca0b795baca05588591.png
[https_algorithms.tutorialhorizon.com_construct-a-binary-tree-from-given-inorder-and-postorder-traversal]: https://algorithms.tutorialhorizon.com/construct-a-binary-tree-from-given-inorder-and-postorder-traversal/