【C++】29行递归重建+队列层序遍历

class Solution {
public:
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        vector<int> res;
        if(xianxu.empty()) return res;
        TreeNode* tree = helper(xianxu, 0, xianxu.size() - 1, zhongxu, 0, zhongxu.size() - 1); //得到重建树
        list<TreeNode*> l; //用列表来层序遍历
        l.push_back(tree);
        int count = 1; //记录每轮取出一层的节点数
        while(!l.empty()) {
            for(int i = 1; i <= count; i++) { //按照每层节点数遍历
                if(l.front()->left) l.push_back(l.front()->left); 
                if(l.front()->right) l.push_back(l.front()->right);
                if(i == count) res.push_back(l.front()->val); //若是这一层最右节点则记录数值
                l.pop_front(); //取出队头
            }
            count = l.size(); //一层遍历完计数更新为下一层节点数
        }
        return res;
    }
    TreeNode* helper(vector<int> &pre, int p_l, int p_r, vector<int> &vin, int v_l, int v_r) {
        TreeNode* res = new TreeNode(pre[p_l]); //可知前序遍历第一位为父节点
        int father = v_l - 1;
        while(pre[p_l] != vin[++father]); //找到中序遍历中父节点的位置
        if(father > v_l) res->left = helper(pre, p_l + 1, p_l + father - v_l, vin, v_l, father - 1); //有左子节点的情况下，左子节点指针指向递归构建的新节点
        if(father < v_r) res->right = helper(pre, p_l + father - v_l + 1, p_r, vin, father + 1, v_r); //有右子节点的情况下，右子节点指针指向递归构建的新节点
        return res; //返回父节点
    }
};