L2-011玩转二叉树

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

// 定义二叉树节点结构
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 根据中序遍历和前序遍历重建二叉树
TreeNode* buildTree(int* preorder, int preStart, int preEnd, int* inorder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) return NULL;

    // 前序遍历的第一个节点是根节点
    
    int rootVal = preorder[preStart];
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = rootVal;
    root->left = root->right = NULL;

    // 在中序遍历中找到根节点的位置
    int rootIndex = inStart;
    while (inorder[rootIndex] != rootVal) rootIndex++;

    // 计算左子树的节点数量
    int leftTreeSize = rootIndex - inStart;

    // 递归构建左子树和右子树
    root->left = buildTree(preorder, preStart + 1, preStart + leftTreeSize, inorder, inStart, rootIndex - 1);
    root->right = buildTree(preorder, preStart + leftTreeSize + 1, preEnd, inorder, rootIndex + 1, inEnd);

    return root;
}

// 对二叉树进行镜面反转
void mirrorTree(TreeNode* root) {
    if (root == NULL) return;

    // 交换左右子树
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;

    // 递归反转左右子树
    mirrorTree(root->left);
    mirrorTree(root->right);
}

// 层序遍历二叉树
void levelOrder(TreeNode* root) {
    if (root == NULL) return;

    // 使用队列实现层序遍历
    TreeNode* queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;//入队

    while (front < rear) {
        TreeNode* node = queue[front++];//出队
        printf("%d", node->val);

        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;

        if (front < rear) printf(" ");
    }
}

int main() {
    int N;
    scanf("%d", &N);

    int inorder[30], preorder[30];
    for (int i = 0; i < N; i++) scanf("%d", &inorder[i]);
    for (int i = 0; i < N; i++) scanf("%d", &preorder[i]);

    // 重建二叉树
    TreeNode* root = buildTree(preorder, 0, N - 1, inorder, 0, N - 1);

    // 镜面反转二叉树
    mirrorTree(root);

    // 输出反转后的层序遍历
    levelOrder(root);

    return 0;
}