从数组中构建二叉树

#include <iostream>
#include <sstream>
#include <stack>
#include <vector>
#include <queue>
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) {}
};

TreeNode* buildTree(vector<int>& nums){
    vector<TreeNode*> vecTree(nums.size(), nullptr);
    for(int i=0; i<nums.size(); i++){
        if(nums[i] != -1){
            vecTree[i] = new TreeNode(nums[i]);
        }
    }
    // i为节点时，左子树为2*i+1，右节点为2*i+2
    for(int i=0; 2*i+1 < nums.size(); ++i){
        if(vecTree[i] != nullptr){
            vecTree[i]->left = vecTree[2*i+1];
            if(2*i+2 < vecTree.size()){
                vecTree[i]->right = vecTree[2*i+2];
            }
        }
    }
    return vecTree[0];
}

TreeNode* buildTreeDFS(const vector<int>& nums, int index){
    if(index >= nums.size() || nums[index] == -1) return nullptr;   // 空节点
    TreeNode* node = new TreeNode(nums[index]);
    node->left = buildTreeDFS(nums, index*2 +1);
    node->right = buildTreeDFS(nums, index*2 +2);
    return node;
}

TreeNode* buildTreeQueue(vector<int>& nums){
    queue<TreeNode*> que;
    TreeNode* root=nullptr;
    if(!nums.empty()) {
        root = new TreeNode(nums[0]);
        que.push(root);
    }
    int idx=0;
    while(!que.empty()){
        int len = que.size();
        for(size_t i=0; i< len;++i){
            auto cur = que.front();que.pop();
            if(nums[idx] == -1) {
                ++idx;
                continue;
            }
            cout << cur->val << " ";
            // 当前节点的左节点
            if((idx*2+1 < nums.size()) && nums[idx*2+1] != -1){
                cur->left = new TreeNode(nums[idx*2+1]);
                que.push(cur->left);
            }
            // 当前节点的右节点
            if((idx*2+2 < nums.size()) && nums[idx*2+2] != -1){
                cur->right = new TreeNode(nums[idx*2+2]);
                que.push(cur->right);
            }
            ++idx;
        }
        cout << endl;
    }
    return root;
}
void travesal(TreeNode* root){
    queue<TreeNode*> que;
    if(root) que.push(root);
    while(!que.empty()){
        int len = que.size();
        for(size_t i=0; i< len;++i){
            auto cur = que.front();que.pop();
            cout << cur->val << " ";
            if(cur->left) que.push(cur->left);
            if(cur->right) que.push(cur->right);
        }
        cout << endl;
    }
}

string deleteSpace(string s){
    size_t l=0, r=0;
    for(; r < s.size(); ++r){
        if(s[r] != ' ') s[l++] = s[r];
    }
    return s.substr(0, l);
}

/*

[1,2,3,-1,4]
[1,2,3,-1,4,5,-1,-1, -1, 6]
[1, 2,3, 4,5]
*/
int main()
{

    // string input;
    // std::getline(cin, input);
    // input = deleteSpace(input);
    // input = input.substr(input.find_first_of('[') + 1, input.find_first_of(']') - input.find_first_of('[') - 1);
    // cout << input << endl;
    // stringstream ss(input);
    // string temp;
    // vector<int> nums;
    // while(getline(ss, temp, ',')){
    //     if(!temp.empty())
    //         nums.emplace_back(stoi(temp));
    // }


    // for(auto& n:nums){
    //     cout << n <<" ";
    // }
    // cout << endl;


    vector<int> nums{1,2,3,-1,4,5,-1,-1, -1, 6};
    // TreeNode* root = buildTree(nums);
    // TreeNode* root = buildTreeQueue(nums);
    TreeNode* root = buildTreeDFS(nums,0);
    
    travesal(root);
}