腾讯c++开发（KPI面）

/*
 * @Description: 
 * @Author: suyunzheng
 * @Date: 2021-09-14 13:39:58
 * @LastEditTime: 2021-09-14 13:45:08
 * @LastEditors: maple
 */


#include <iostream>
#include <vector>

#include <queue>


using namespace std;

struct TreeNode{
    int val;

    TreeNode* left;
    TreeNode* right;

    TreeNode(int a ):val(a),left(nullptr), right(nullptr){;}


}; 
TreeNode* build(const vector<int>& in_vec,int in_left, int in_right,  const vector<int>& pos_vec, int pos_left, int pos_right ){

    if(in_left > in_right){
        return nullptr;
    }
    if(pos_left > pos_right){
        return nullptr;
    }
    
    TreeNode* root = new TreeNode(pos_vec[pos_right]);
    
    int i = 0;
    for(; i<in_vec.size(); i++){
        if(in_vec[i]==pos_vec[pos_right]){
            break;
        }
    }
    cout << "i: " << i << endl;

    root->left = build(in_vec, in_left, i-1, pos_vec, pos_left, pos_left+i-in_left-1);
    root->right = build(in_vec, i+1, in_right, pos_vec, pos_left+i-in_left , pos_right-1);

    return root;

}

void printTree(TreeNode* root){
    queue<TreeNode*> q;
    if(root){
        q.push(root);
    }

    while(!q.empty()){
        int len = q.size();
        while(len-->0){
            auto node = q.front();
            q.pop();
            cout << node->val << " ";
            
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
        cout << endl;
    }
}

int main() {
    //int a;
    //cin >> a;
    vector<int> in_vec = {9, 3, 15, 20, 7};
    vector<int> pos_vec = {9, 15, 7, 20, 3};

    auto root = build(in_vec, 0, in_vec.size()-1, pos_vec, 0, pos_vec.size()-1);

    printTree(root);
}