根据前序遍历和中序遍历计算后序遍历，根据中序遍历和后序遍历计算前序遍历，递归方法

JavaTest.java

package test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class JavaTest {

    private static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            super();
            this.value = value;
        }
    }

    public static void main(String[] args) {
        List<Integer> preOrder = Arrays.asList(1, 2, 4, 5, 3, 6, 7);
        List<Integer> midOrder = Arrays.asList(4, 2, 5, 1, 6, 3, 7);
        List<Integer> postOrder = Arrays.asList(4, 5, 2, 6, 7, 3, 1);

        Node computedTreePostOrder = computePostOrderByPreOrderAndMidOrder(preOrder, midOrder);
        List<Integer> computedPostOrder = new LinkedList<>();
        printTreePostOrder(computedTreePostOrder, computedPostOrder);
        if (!computedPostOrder.equals(postOrder)) {
            throw new RuntimeException("computed post order wrong");
        } else {
            System.out.println("compute post order successfully");
        }

        Node computedTreePreOrder = computePreOrderByMidOrderAndPostOrder(midOrder, postOrder);
        List<Integer> computedPreOrder = new LinkedList<>();
        printTreePreOrder(computedTreePreOrder, computedPreOrder);
        if (!computedPreOrder.equals(computedPreOrder)) {
            throw new RuntimeException("computed pre order wrong");
        } else {
            System.out.println("compute pre order successfully");
        }
    }

    private static Node computePostOrderByPreOrderAndMidOrder(List<Integer> preOrder,
            List<Integer> midOrder) {
        if (preOrder.isEmpty()) {
            return null;
        }
        int rootValue = preOrder.get(0);
        int rootIndexInMidOrder = 0;
        for (int temp : midOrder) {
            if (temp == rootValue) {
                break;
            }
            rootIndexInMidOrder++;
        }

        List<Integer> leftChildPreOrder = new LinkedList<>();
        List<Integer> leftChildMidOrder = new LinkedList<>();
        for (int i = 0; i < rootIndexInMidOrder; i++) {
            leftChildPreOrder.add(preOrder.get(i + 1));
            leftChildMidOrder.add(midOrder.get(i));
        }

        List<Integer> rightChildPreOrder = new LinkedList<>();
        List<Integer> rightChildMidOrder = new LinkedList<>();
        for (int i = rootIndexInMidOrder + 1; i < midOrder.size(); i++) {
            rightChildPreOrder.add(preOrder.get(i));
            rightChildMidOrder.add(midOrder.get(i));
        }

        Node root = new Node(rootValue);
        root.left = computePostOrderByPreOrderAndMidOrder(leftChildPreOrder, leftChildMidOrder);
        root.right = computePostOrderByPreOrderAndMidOrder(rightChildPreOrder, rightChildMidOrder);

        return root;
    }

    private static Node computePreOrderByMidOrderAndPostOrder(List<Integer> midOrder,
            List<Integer> postOrder) {
        if (postOrder.isEmpty()) {
            return null;
        }

        int rootValue = postOrder.get(postOrder.size() - 1);
        int rootIndexInMidOrder = 0;
        for (int temp : midOrder) {
            if (temp == rootValue) {
                break;
            }
            rootIndexInMidOrder++;
        }

        List<Integer> leftChildPostOrder = new LinkedList<>();
        List<Integer> leftChildMidOrder = new LinkedList<>();
        for (int i = 0; i < rootIndexInMidOrder; i++) {
            leftChildPostOrder.add(postOrder.get(i));
            leftChildMidOrder.add(midOrder.get(i));
        }

        List<Integer> rightChildPostOrder = new LinkedList<>();
        List<Integer> rightChildMidOrder = new LinkedList<>();
        for (int i = rootIndexInMidOrder + 1; i < midOrder.size(); i++) {
            rightChildPostOrder.add(postOrder.get(i - 1));
            rightChildMidOrder.add(midOrder.get(i));
        }

        Node root = new Node(rootValue);
        root.left = computePreOrderByMidOrderAndPostOrder(leftChildMidOrder, leftChildPostOrder);
        root.right = computePreOrderByMidOrderAndPostOrder(rightChildMidOrder, rightChildPostOrder);

        return root;
    }

    private static void printTreePostOrder(Node root, List<Integer> result) {
        if (null == root) {
            return;
        }

        printTreePostOrder(root.left, result);
        printTreePostOrder(root.right, result);
        result.add(root.value);
    }

    private static void printTreePreOrder(Node root, List<Integer> result) {
        if (null == root) {
            return;
        }

        result.add(root.value);
        printTreePostOrder(root.left, result);
        printTreePostOrder(root.right, result);
    }

}