NC204382 中序序列

前序遍历的顺序是根左右，我们可以确定数组中的第一个元素就是根节点，根节点后面的元素是左子树还是右子树呢，我们并不清楚，但是题目上说了，如果某个节点只有一个子节点那么这个子节点就是左节点，所以我们就确定了，根节点后面的节点就一定是左子树的节点。既然左子树的节点确定了，我们就在后序遍历中找到这个节点，区分左子树和右子树，进而就可以求出来中序遍历结果了。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int 二叉树节点数量
     * @param pre intvector 前序序列
     * @param suf intvector 后序序列
     * @return intvector
     */
    vector<int>res;
    void deal(vector<int>& pre, vector<int>& suf, int l1, int r1, int l2, int r2) {
        if (l1 > r1)return;
        if (l1 == r1) {
            res.push_back(pre[l1]);
            return;
        }
        int pos = 0;
        for (int i = l2; i <= r2; i++) {
            if (suf[i] == pre[l1 + 1]) {
                pos = i;
                break;
            }
        }
        deal(pre, suf, l1 + 1, l1 + 1 + pos - l2, l2, pos);
        res.push_back(pre[l1]);
        deal(pre, suf, l1 + 1 + pos - l2 + 1, r1, pos + 1, r2 - 1);
    }
    vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
        // write code here
        deal(pre, suf, 0, n - 1, 0, n - 1);
        return res;
    }
};