根据输入构造二叉树，输出该二叉树的先序序列。二叉树共有N个节点，节点编号是1到N。约定1号节点是根节点。C语言代码

假设输入数据格式如下：

- 第1行是一个整数N，表示二叉树的节点数；
- 接下来N行，每行包含三个整数，分别是该节点的编号、左子节点的编号（如果没有左子节点则为0）、右子节点的编号（如果没有右子节点则为0）。

那么我们可以按照以下步骤来解决这个问题：

1. 定义二叉树节点结构体

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

2. 定义递归函数 `buildTree`

struct TreeNode* buildTree(int* preorder, int* inorder, int inorderStart, int inorderEnd, unordered_map<int, int>* inorderMap) {
    static int preIndex = 0;

    if (inorderStart > inorderEnd) {
        return NULL;
    }

    int rootVal = preorder[preIndex++];
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootVal;

    int inorderIndex = (*inorderMap)[rootVal];
    int leftTreeSize = inorderIndex - inorderStart;

    root->left = buildTree(preorder, inorder, inorderStart, inorderIndex - 1, inorderMap);
    root->right = buildTree(preorder, inorder, inorderIndex + 1, inorderEnd, inorderMap);

    return root;
}

3. 读入输入数据，构建二叉树

int n;
scanf("%d", &n);

int preorder[n];
int inorder[n];
unordered_map<int, int> inorderMap;

for (int i = 0; i < n; i++) {
    int val, left, right;
    scanf("%d %d %d", &val, &left, &right);
    preorder[i] = val;
    inorder[i] = val;
    inorderMap[val] = i;
}

sort(inorder, inorder + n);
struct TreeNode* root = buildTree(preorder, inorder, 0, n - 1, &inorderMap);

4. 输出先序序列

void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    printf("%d ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

preorderTraversal(root);

完整代码如下：