#include <stdlib.h>
struct QueueNode 
{
    struct TreeNode* Tree_Node;
    struct QueueNode* next;
};

struct Queue 
{
    struct QueueNode* front;
    struct QueueNode* rear;
    int length;
};

// 创建一个空队列
struct Queue* Queue_create() 
{
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = queue->rear = NULL;
    queue->length = 0;
    return queue;
}

// 入队
void Queue_in(struct Queue* queue, struct TreeNode* Tree_Node) 
{
    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newNode->Tree_Node = Tree_Node;
    newNode->next = NULL;

    if (queue->length == 0) 
    {
        queue->front = queue->rear = newNode;
    } else 
    {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    queue->length++;
}

// 出队
struct TreeNode* Queue_out(struct Queue* queue) {
    if (queue->length == 0) 
    {
        return NULL;
    }

    struct TreeNode* Tree_Node = queue->front->Tree_Node;
    struct QueueNode* temp = queue->front;

    queue->front = queue->front->next;

    if (queue->front == NULL) 
    {
        queue->rear = NULL;
    }

    free(temp);
    queue->length--;
    return Tree_Node;
}

 /** *******************************************************************************************
 * @brief   根据前序和中序构建二叉树
 * @param preOrder int整型一维数组 先序遍历
 * @param preStart int preOrder数组 子树起始下标
 * @param preEnd int preOrder数组 子树结束下标
 * @param inOrder int整型一维数组 中序遍历
 * @param vinStart int inOrder数组 子树起始下标
 * @param vinEnd int inOrder数组 子树结束下标
 * @return struct TreeNode* 二叉树根节点
 *********************************************************************************************/
 struct TreeNode* buildTree(int* preOrder, int preStart, int preEnd, int* inOrder, int vinStart, int vinEnd) {
    if(preStart > preEnd || vinStart > vinEnd)
    {
        return NULL;
    }
    
    // 根节点的值为前序遍历的第一个元素
    int rootVal = preOrder[preStart];
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootVal;
    root->left = root->right = NULL;
    
    // 在中序遍历数组中找到根节点的位置
    int rootIdx = vinStart;
    while(rootIdx <= vinEnd)
    {
        if(rootVal == inOrder[rootIdx])
        {
            break;
        }
        rootIdx++;
    }
    
    // 左右子树的节点数
    int leftLen = rootIdx - vinStart;
    int rightLen = vinEnd - rootIdx;
    
    /* 递归构建左子树和右子树:
        左子树的前序和中序
        右子树的前序和中序
    */
    root->left = buildTree(preOrder, preStart + 1, preStart + leftLen,  inOrder, vinStart,  rootIdx - 1);
    root->right = buildTree(preOrder, preStart + leftLen + 1, preEnd, inOrder,  rootIdx + 1, vinEnd);
    
    return root;
}

/************************************************************************************************
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求二叉树的右视图
* @author Senky
 * @date 2023.08.20
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief   
 *          ①首先通过给定前序遍历和中序遍历的结果来重建二叉树
 *          ②使用层序遍历将最后一个结点存储在结果数组
 * @param preOrder int整型一维数组 先序遍历
 * @param preOrderLen int preOrder数组长度
 * @param inOrder int整型一维数组 中序遍历
 * @param inOrderLen int inOrder数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 * *********************************************************************************************/
int* solve(int* preOrder, int preOrderLen, int* inOrder, int inOrderLen, int* returnSize ) {
    // write code here
    int* result = (int*)calloc(1,sizeof(int));//一个int类型空间,初始化为0
    *returnSize = 0;//行数默认为0

    /*每一个值都必须是合法值-即不是空树*/
    if(NULL == preOrder || NULL == inOrder || preOrderLen != inOrderLen || preOrderLen < 0)
    {
        return NULL;
    }

    //构建二叉树
    struct TreeNode* root = buildTree(preOrder, 0, preOrderLen - 1, inOrder, 0, inOrderLen - 1);

    //创建空队列
    struct Queue* queue = Queue_create();

    //根节点入队
    Queue_in(queue, root);

    //当前层序遍历层数的结点个数
    int levelNodes = 1;

    //当前层数(从0开始)
    int currentlevel = 1;

    //层序遍历
    while (queue->length != 0) 
    {
        //当前层结点个数
        levelNodes = queue->length;

        for (int i = 0; i < levelNodes; i++) 
        {
            struct TreeNode* node = Queue_out(queue);

            //当前层的最后一个元素存入数组,数组长度+1
            if(i == levelNodes - 1)
            {
                result[*returnSize] = node->val;//结点数据入数组,行数加一
                result = (int*)realloc(result,(++currentlevel)*sizeof(int));//数组根据层数扩展
                (*returnSize)++;
            }

            //左右子树入队
            if (node->left) 
            {
                Queue_in(queue, node->left);
            }
            if (node->right) 
            {
                Queue_in(queue, node->right);
            }
        }
        
    }

    free(queue);
    return result;
}

TIPS:

这一题的综合型很强,包括了

①前序中序转换成二叉树(递归)

②将二叉树层序遍历(队列操作)

前面的几道题刷完后这题其实也不难