Input:

第一行为节点的数量 $n$（包括空节点），其中 $n=2^{层数}-1$；
第二行包含 $n$ 个数，表示每个节点的值（层序遍历的顺序），其中 $-1$ 表示节点为空节点。

15
4 1 6 0 2 5 7 -1 -1 -1 3 -1 -1 -1 8

Output:

4 1 0 2 3 6 5 7 8 

Code:

#include <iostream>
#include <vector>

using namespace std;

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

int n;

TreeNode* tree() {
    cin >> n;
    if (!n) return nullptr;

    vector<TreeNode*> nodes(n, nullptr);
    for (int i = 0, x; i < n; i ++ ) {
        cin >> x;
        if (x != -1) nodes[i] = new TreeNode(x);
    }
    for (int i = 0; i < n / 2; i ++ ) {
        nodes[i]->left = nodes[i * 2 + 1];
        nodes[i]->right = nodes[i * 2 + 2];
    }
    return nodes[0];
}

void dfs(TreeNode *root) {
    if (!root) return;
    cout << root->val << ' ';
    dfs(root->left), dfs(root->right);
}

int main() {
    auto root = tree();
    dfs(root);
    return 0;
}