峡大学数据结构考研真题

// 2023年真题参考答案（先序+中序重建二叉树）
typedef struct TreeNode {
    char val;
    struct TreeNode left;
    struct TreeNode right;
} TreeNode;
TreeNode buildTree(char preorder, char inorder, int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd) return NULL;
    TreeNode root = (TreeNode)malloc(sizeof(TreeNode));
    root->val = preorder[preStart];
    root->left = root->right = NULL;
    // 在中序序列中找到根结点位置
    int rootIndex = inStart;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == preorder[preStart]) {
            rootIndex = i;
            break;
        }
    }
    // 递归构建左右子树
    int leftSize = rootIndex 
- inStart;
    root->left = buildTree(preorder, inorder, preStart+1, preStart+leftSize, inStart, rootIndex-1);
    root->right = buildTree(preorder, inorder, preStart+leftSize+1, preEnd, rootIndex+1, inEnd);
    return root;
}

// 2023年真题参考答案（三数取中快速排序划分）
int partitionMedianOfThree(int arr[], int low, int high) {
    int mid = low + (high 
- low) / 2;
    // 三数取中：将中位数移到low位置
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    if (arr[low] > arr[high]) swap(arr, low, high);
    if (arr[mid] > arr[high]) swap(arr, mid, high);
    int pivot = arr[low];
    int i = low, j = high + 1;
    // 双指针扫描
    while (true) {
        while (arr[++i] < pivot) if (i == high) break;
        while (arr[--j] > pivot) if (j == low) break;
        if (i >= j) break;
        swap(arr, i, j);
    }
    swap(arr, low, j);
    return j;
}

// 2022年真题参考答案（非递归中序遍历）
void inorderWithoutRecursion(TreeNode root) {
    if (!root) return;
    stack s;
    TreeNode current = root;
    while (current || !s.empty()) {
        // 一直向左走到底
        while (current) {
            s.push(current);
            current = current->left;
        }
        // 访问栈顶结点
        current = s.top();
        s.pop();
        printf("%c ", current->val);
        // 转向右子树
        current = current->right;
    }
}