中序序列

思路

易知：

前序遍历顺序为：根、左子树、右子树；
中序遍历顺序为：左子树、根、右子树；
后序遍历顺序为：左子树、右子树、根；

由前序遍历可知，整棵树的根节点是 。

对于样例：

3 2 1 4 5
1 5 4 2 3

结合前序、后序遍历可得整棵树的结构：

得到规律：

在先序遍历序列中，根节点之后是左儿子结点；在后序遍历序列中，根节点之前是右儿子结点。

枚举先序遍历中的节点，结合其在后序遍历中的位置，判断其子树所包含节点范围，递归求解即可。

Code

class Solution{
private:
    vector<int> ans;
    vector<int> pre, suf;
    struct node {
        int val;
        node *lson = NULL, *rson = NULL;
    };

public:
    node *build(int l1, int r1, int l2, int r2) {
        if (l1 > r1) return nullptr;
        node *cur = new node();
        cur->val = pre[l1];
        if (l1 == r1) return cur;
        int pos;
        for (int i = l2; i <= r2; ++i) {
            if (pre[l1 + 1] == suf[i]) {
                pos = i;
                break;
            }
        }
        cur->lson = build(l1 + 1, pos - l2 + l1 + 1, l2, pos);
        cur->rson = build(pos - l2 + l1 + 2, r1, pos + 1, r2 - 1);
        return cur;
    }

    void dfs(node *cur) {
        if (cur == NULL) return ;
        dfs(cur->lson);
        ans.push_back(cur->val);
        dfs(cur->rson);
    }

    vector<int> solve(int n, vector<int> npre, vector<int> nsuf) {
        pre.push_back(0);
        suf.push_back(0);
        for (int i = 0; i < n; ++i) {
            pre.push_back(npre[i]);
            suf.push_back(nsuf[i]);
        }
        node *root = build(1, n, 1, n);
        dfs(root);
        return ans;
    }
};

优化

在上述思路的基础上，去掉建树过程，可直接在数组上递归求解。

Code

  class Solution {
public:
    /**
     * 返回所求中序序列
     * @param n int整型 二叉树节点数量
     * @param pre int整型vector 前序序列
     * @param suf int整型vector 后序序列
     * @return int整型vector
     */
    vector<int>in;
    void build(int pl, int pr, int sl, int sr, vector<int>& pre, vector<int>& post, int l=0,int r=0)
    {
        if (pl > pr || sl > sr)
            return;
        int i;
        for (i = sr - 1; i >= sl && post[i] != pre[pl + 1]; i--);
        int left = i - sl + 1;
        in[l + left] = pre[pl];
        build(pl + 1, pl + left, sl, i, pre, post,l);
        build(pl + left + 1, pr, i + 1, sr - 1, pre,post, l+left+1);
    }
    vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
        // write code here
        in = vector<int>(n);
        build(0, n - 1, 0, n - 1, pre, suf);
        return in;
    }
};