从已知数组构建二叉树 2023-05-05

作为考官，面试常会考察应试者二叉树遍历相关算法，出提示。突发奇想，如果给定一个数组，如何将已知数据构建成二叉树，思考5秒觉得还上有一定的难度。并且网上刷题也少有类似代码；

简单写了一段，宽度优先构建方式。

struct BTree {
    double data;
    BTree* ltree;
    BTree* rtree;
};


std::vector<double> data_array(0, 100);

Btree* head = nullptr;

bool TreeConstruct(std::vector<double>* data_aray, Btree* head) {
    if (!data_array) {
        return false;
    }
    std::queue<BTree*> que;
    BTree* head = new BTree;

    que.push_back(head);
    for (int i = 0; i < data_array.size(); i++) {
        if (que.is_empty()) {
            break;
        }
        BTree* tmp_node =que.begin();
        que.pop();

        tmp_node->data = data_array.at(i);
        if (que.size() <= data_array.size() - i - 1) {
            BTree* lnode = new BTree;
            que.push_back(lnode);
            tmp_node->ltree = lnode;
        }
        if (que.size() < data_array.size() - i - 1) {
            BTree* lnode = new BTree;
            BTree* rnode = new BTree;
            que.push_back(lnode);
            que.push_back(rnode);
            tmp_node->ltree = lnode;
            tmp_node->rtree = rnode;
        }
    }
    return true;
}