题目：
用先序序列和中序序列构建二叉树，采用二叉链表存储。编写递归算法，交换二叉树的左右子树，
输出新二叉树按先序遍历得到的结果。

提交格式：实现void solve(int n, int *preOrder, int *inOrder, int *outOrder)函数。
函数参数为序列长度n、先序序列preOrder、中序序列inOrder和输出序列outOrder。1<=n<=1000000，树的深度<=2000。
请不要printf输出任何内容。

输入样例1：
n=5,preOrder={1,2,3,4,5},inOrder={3,2,4,1,5}
输出样例1：
outOrder={1,5,2,4,3}

解答：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

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

// 动态哈希表实现
typedef struct {
    int key;
    int value;
} HashEntry;

typedef struct {
    HashEntry* entries;
    int capacity;
    int size;
} HashMap;

// 创建哈希表
HashMap* createHashMap(int initialCapacity) {
    HashMap* map = (HashMap*)malloc(sizeof(HashMap));
    map->entries = (HashEntry*)calloc(initialCapacity, sizeof(HashEntry));
    map->capacity = initialCapacity;
    map->size = 0;
    return map;
}

// 哈希函数
unsigned int hash(int key, int capacity) {
    return (unsigned int)(key * 2654435761) % capacity;
}

// 插入键值对
void hashMapInsert(HashMap* map, int key, int value) {
    if (map->size >= map->capacity / 2) {
        // 扩容
        int newCapacity = map->capacity * 2;
        HashEntry* newEntries = (HashEntry*)calloc(newCapacity, sizeof(HashEntry));
        
        for (int i = 0; i < map->capacity; i++) {
            if (map->entries[i].key != 0 || map->entries[i].value != 0) { // 简单判断非空
                unsigned int h = hash(map->entries[i].key, newCapacity);
                while (newEntries[h].key != 0 || newEntries[h].value != 0) { // 简单判断非空
                    h = (h + 1) % newCapacity;
                }
                newEntries[h] = map->entries[i];
            }
        }
        
        free(map->entries);
        map->entries = newEntries;
        map->capacity = newCapacity;
    }
    
    unsigned int h = hash(key, map->capacity);
    while (map->entries[h].key != 0 || map->entries[h].value != 0) { // 简单判断非空
        if (map->entries[h].key == key) {
            map->entries[h].value = value; // 更新现有键
            return;
        }
        h = (h + 1) % map->capacity;
    }
    
    map->entries[h].key = key;
    map->entries[h].value = value;
    map->size++;
}

// 查找键对应的值
int hashMapFind(HashMap* map, int key) {
    unsigned int h = hash(key, map->capacity);
    while (map->entries[h].key != 0 || map->entries[h].value != 0) { // 简单判断非空
        if (map->entries[h].key == key) {
            return map->entries[h].value;
        }
        h = (h + 1) % map->capacity;
    }
    return -1; // 不应该发生，因为题目保证输入有效
}

// 释放哈希表
void freeHashMap(HashMap* map) {
    free(map->entries);
    free(map);
}

// 根据先序和中序序列构建二叉树
TreeNode* buildTree(int* preOrder, int preStart, int preEnd, int* inOrder, int inStart, int inEnd, HashMap* map) {
    if (preStart > preEnd) {
        return NULL;
    }
    
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = preOrder[preStart];
    
    int inRootIndex = hashMapFind(map, root->val);
    int leftSize = inRootIndex - inStart;
    
    root->left = buildTree(preOrder, preStart + 1, preStart + leftSize, inOrder, inStart, inRootIndex - 1, map);
    root->right = buildTree(preOrder, preStart + leftSize + 1, preEnd, inOrder, inRootIndex + 1, inEnd, map);
    
    return root;
}

// 交换二叉树的左右子树
void swapSubtrees(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    
    swapSubtrees(root->left);
    swapSubtrees(root->right);
}

// 先序遍历二叉树，将结果存入outOrder数组
void preorderTraversal(TreeNode* root, int* outOrder, int* index) {
    if (root == NULL) {
        return;
    }
    
    outOrder[(*index)++] = root->val;
    preorderTraversal(root->left, outOrder, index);
    preorderTraversal(root->right, outOrder, index);
}

// 释放二叉树内存
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

void solve(int n, int *preOrder, int *inOrder, int *outOrder) {
    // 创建哈希表并构建映射
    HashMap* map = createHashMap(16); // 初始容量16
    
    for (int i = 0; i < n; i++) {
        hashMapInsert(map, inOrder[i], i);
    }
    
    // 构建二叉树
    TreeNode* root = buildTree(preOrder, 0, n - 1, inOrder, 0, n - 1, map);
    
    // 释放哈希表
    freeHashMap(map);
    
    // 交换左右子树
    swapSubtrees(root);
    
    // 先序遍历并存储结果
    int index = 0;
    preorderTraversal(root, outOrder, &index);
    
    // 释放二叉树内存
    freeTree(root);
}

AI跑的，满分