【每日刷题】Day62

3. 2415. 反转二叉树的奇数层 - 力扣（LeetCode）

//思路：暴力求解。首先层序遍历将二叉树中的值存入数组中，因为是完美二叉树，因此我们很容易可以知道二叉树奇数层在数组中的区域。对数组中属于二叉树奇数层区域的数据进行翻转。翻转后的数组再进行层序遍历存回二叉树中。

typedef struct TreeNode TN;

 

typedef struct listnode

{

    struct TreeNode* val;

    struct listnode* next;

}LN;

struct TreeNode* reverseOddLevels(struct TreeNode* root)

{

    int* arr = (int*)malloc(sizeof(int)*20000);

    int count = 1;

//层序遍历存入数组↓↓↓

    LN* phead = (LN*)malloc(sizeof(LN));

    LN* ptail = phead;

    LN* node = (LN*)malloc(sizeof(LN));

    node->val = root;

    node->next = NULL;

    ptail->next = node;

    ptail = ptail->next;

    while(phead!=ptail)

    {

        struct TreeNode* tmp = phead->next->val;

        phead = phead->next;

        arr[count++] = tmp->val;

        if(tmp->left)

        {

            LN* node = (LN*)malloc(sizeof(LN));

            node->val = tmp->left;

            node->next = NULL;

            ptail->next = node;

            ptail = ptail->next;

        }

        if(tmp->right)

        {

            LN* node = (LN*)malloc(sizeof(LN));

            node->val = tmp->right;

            node->next = NULL;

            ptail->next = node;

            ptail = ptail->next;

        }

    }

//层序遍历存入数组↑↑↑

//数组翻转↓↓↓

    int flag = 2;

    while(flag

    {

        int flag1 = flag*2-1;

        int flag2 = flag1;

        while(flag

        {

            int tmp = arr[flag];

            arr[flag] = arr[flag1];

            arr[flag1] = tmp;

            flag++;

            flag1--;

        }

        flag = (flag2+1)*2;

    }

//数组翻转↑↑↑

//层序遍历回放二叉树↓↓↓

    LN* phead1 = (LN*)malloc(sizeof(LN));

    LN* ptail1 = phead1;

    LN* node1 = (LN*)malloc(sizeof(LN));

    node1->val = root;

    node1->next = NULL;

    ptail1->next = node1;

    ptail1 = ptail1->next;

    int count1 = 1;

    while(count1

    {

        struct TreeNode* tmp = phead1->next->val;

        phead1 = phead1->next;

        tmp->val = arr[count1++];

        if(count1left)

        {

            LN* node = (LN*)malloc(sizeof(LN));

            node->val = tmp->left;

            node->next = NULL;

            ptail1->next = node;

            ptail1 = ptail1->next;

        }

        if(count1right)

        {

            LN* node = (LN*)malloc(sizeof(LN));

            node->val = tmp->right;

            node->next = NULL;

            ptail1->next = node;

            ptail1 = ptail1->next;

        }

    }

    return root;

}