浅析 NC204382 中序序列

题目链接：

https://ac.nowcoder.com/acm/problem/204382

题面：

给定一棵有n个结点的二叉树的先序遍历与后序遍历序列，求其中序遍历序列。 若某节点只有一个子结点，则此处将其看作左儿子结点（示意图和样例见题） 1≤n≤100,000

代码+解析：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 二叉树节点数量
     * @param pre intvector 前序序列
     * @param suf intvector 后序序列
     * @return i  ntvector
     */
    
    vector<int> zhong;
    
    void deal(int pre_l, int pre_r, int suf_l, int suf_r, vector<int>& pre, vector<int>& suf) {
        
        if (pre_l > pre_r) {  
            return ;   
        }
        
        if (pre_l == pre_r) {    // 子树递归出口
            zhong.push_back(pre[pre_l]);    // 若某节点只有一个子结点，则此处将其看作左儿子结点，恰好中序遍历是：左-根-右，先遍历左子树
            return ;   
        }        
        
        int next_root = pre[pre_l+1];
        
        // 前序遍历子序列的当前根节点 pre[pre_l] 对应的位置的下一个数 next_root 是 下一棵子树的根， 
        // 而 这个下一棵子树是左子树还是右子树 取决于 下一棵子树的根在后序遍历子序列的划分 (suf[ptr_suf] == next_root) （下下棵子树的左子树的最右侧节点）
        
        int ptr_suf = suf_l;
        for (; ptr_suf <= suf_r; ptr_suf++) {
            if (suf[ptr_suf] == next_root) {  
                break;
            }
        }
        
        // 左子树
        deal(pre_l + 1, pre_l + 1 + (ptr_suf - suf_l), suf_l, ptr_suf, pre, suf);
        
        // 当前 根
        zhong.push_back(pre[pre_l]);
        
        // 右子树
        deal(pre_r - ((suf_r - 1) - (ptr_suf + 1)), pre_r, ptr_suf + 1, suf_r - 1, pre, suf);
                            
    }
    
    
    
    vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
        // write code here
        // 若只已知 前序遍历序列 和 后序遍历序列，条件强度是不够的解题的。因为前序：根-左-右，后序：左-右-根。每颗子树的根都好确定，不能分清左右子树
        // 题目强化条件：若某节点只有一个子结点，则此处将其看作左儿子结点，这样就可以利用其衍生的叶子节点无左右子树等特征来划分。
        
        deal(0, n-1, 0, n-1, pre, suf);
        
        return zhong;

    }
};