1. 通过先序和中序数组生成后序数组

1.1. 问题

已知一棵二叉树所有的节点值都不同，给定这棵树正确的先序和中序数组，不要重建整棵树，而是通过这两个数组直接生成正确的后序数组。

1.2. 思路

• 当一个序列是二叉树的先序遍历结果时，那么根节点的值在序列最前面。
• 当一个序列是二叉树的中序遍历结果时，位于根节点值左边的子序列是二叉树左子树的序列，位于根节点右边的子序列是二叉树的右子树的序列。

因此可以通过递归的方式进行处理。

1.3. 代码

感觉书上的版本更好，使用了一个hashmap记录了中序数组每个元素所在的位置，并且还使用了方法的返回值表示接下来需要填充的起始位置。

1.3.1. 我的版本

    public int[] postArr(int[] preArr, int[] midArr) {
        int len = preArr.length;
        int[] res = new int[len];
        int[] pos = {(len - 1)};
        process(res, pos, preArr, 0, len - 1, midArr, 0, len - 1);
        return res;
    }


    private void process(int[] res, int[] pos, int[] preArr, int ps, int pe, int[] midArr, int ms, int me) {
        if (ps > pe) return;
        res[pos[0]--] = preArr[ps];
        int lps, lpe, rps, rpe, lms, lme, rms, rme;
        lps = lpe = rps = rpe = lms = lme = rms = rme = 0;

        for (int i = ms; i <= me; i++) {
            if (preArr[ps] == midArr[i]) {
                lps = ps + 1;
                lpe = ps + i - ms;
                rps = lpe + 1;
                rpe = pe;
                lms = ms;
                lme = i - 1;
                rms = i + 1;
                rme = me;
                break;
            }
        }
        process(res, pos, preArr, rps, rpe, midArr, rms, rme);
        process(res, pos, preArr, lps, lpe, midArr, lms, lme);
    }

1.3.2. 书上的版本

    public int[] getPosArray(int[] pre, int[] in) {
        if (pre == null || in == null) {
            return null;
        }
        int len = pre.length;
        int[] pos = new int[len];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>()
        for (int i = 0; i < len; i++) {
            map.put(in[i], i);
        }
        setPos(pre, 0, len - 1, in, 0, len - 1, pos, len - 1, map);
        return pos;
    }
    // 从右往左依次填好后序数组 s
    // si 为后序数组 s 该填的位置
    // 返回值为 s 该填的下一个位置
    public 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);
    }