#include<stdcpp.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

void create(int * val, int cnt, TreeNode *cur,int idx){
    int left_idx = (idx + 1) * 2 - 1;
    int right_idx = (idx + 1) * 2 ;
    if(left_idx > cnt){
        cur->left = nullptr;
        cur->right = nullptr;
        return;
    }
    if(right_idx > cnt){
        cur->right = nullptr;
        return;
    }
    if(val[left_idx] == -1){
        cur -> left = nullptr;
    }else{
        TreeNode * left_child = new TreeNode(val[left_idx]);
        cur->left = left_child;
        create(val,cnt,left_child,left_idx);
    }
    if(val[right_idx] == -1){
        cur -> right = nullptr;
    }else{
        TreeNode * right_child = new TreeNode(val[right_idx]);
        cur->right = right_child;
        create(val, cnt, right_child, right_idx);
    }
    return;
}
void traverse(TreeNode* node){
    cout<<node->val<<' ';
    if(node->left != nullptr){
        traverse(node->left);
    }
    if(node->right != nullptr){
        traverse(node->right);
    }
    return;
}
TreeNode* createTree(int * val, int cnt){
    TreeNode * root = new TreeNode(val[0]);
    cout<<"create a tree"<<endl;
    create(val,cnt,root, 0);
    traverse(root);
    cout<<"\ndone"<<endl;
    // cout<<endl;
    return root;
}
class Solution{
    public:
    vector<int> traversal(TreeNode * node, vector<int> & rlt){
        if(node -> left != nullptr){
            traversal(node->left,rlt);
        }
        rlt.push_back(node->val);
        if(node -> right != nullptr){
            traversal(node->right, rlt);
        }
        return rlt;
    }
    vector<int> inorderTraversal(TreeNode* root){
        vector<int> rlt;
        traversal(root, rlt);
        return rlt;
    }
};
int main(){
    Solution sol;
    int ex1_data[7] = {1,-1,2,-1,-1,3,-1};
    TreeNode * ex1 = createTree(ex1_data, 7);
    vector<int> rltex1 = sol.inorderTraversal(ex1);
    for(int i = 0 ; i < rltex1.size(); i++){
        cout<<rltex1[i]<<' ';
    }
    cout<<endl;

    return 0;
}