分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击http://www.captainbed.net

package live.every.day.DataStructure.Tree.BinaryTree;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 题目：
 * 通过先序和中序数组生成后序数组。
 *
 * 思路：
 * 先设置后序数组最右边的值，再根据右子树和左子树的划分，从右到左依次设置好后序数组的全部位置。
 *
 * @author Created by LiveEveryDay
 */

public class GetPostArrayByPreOrderInOrder {

    public static int[] getPostArray(int[] pre, int[] in) {
        if (pre == null || in == null) {
            return null;
        }
        int len = pre.length;
        int[] post = new int[len];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            map.put(in[i], i);
        }
        setPos(pre, 0, len - 1, in, 0, len - 1, post, len - 1, map);
        return post;
    }

    private static int setPos(int[] p, int pi, int pj, int[] n, int ni, int nj, int[] s, int si, HashMap<Integer, Integer> map) {
        if (pi > pj) {
            return si;
        }
        s[si--] = p[pi];
        int i = map.get(p[pi]);
        si = setPos(p, pj - nj + i + 1, pj, n, i + 1, nj, s, si, map);
        return setPos(p, pi + 1, pi + i - ni, n, ni, i - 1, s, si, map);
    }

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 5, 8, 9, 3, 6, 7};
        int[] in = {4, 2, 8, 5, 9, 1, 6, 3, 7};
        int[] post = getPostArray(pre, in);
        System.out.printf("The post array is: %s", Arrays.toString(post));
    }

}

// ------ Output ------
/*
The post array is: [4, 8, 9, 5, 2, 6, 7, 3, 1]
*/