题解 | #输出二叉树的右视图#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求二叉树的右视图
 * @param preOrder int整型一维数组 先序遍历
 * @param preOrderLen int preOrder数组长度
 * @param inOrder int整型一维数组 中序遍历
 * @param inOrderLen int inOrder数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
struct Tree
{
    int val;
    struct Tree *left;
    struct Tree *right;
};

void resort(int* returnSize, int** returnColumnSizes,int** arr,struct Tree* queue[])
{
    int start=0,end=1;
    for(int row=0;row<*returnSize;row++){
        int temp=end-start;
        *((*returnColumnSizes)+row)=temp;
        arr[row]=malloc((*returnColumnSizes)[row]*sizeof(int));
        for(int i=0;i<temp;i++)
        { 
            arr[row][i]=queue[start]->val;
            if(queue[start]->left) 
            queue[end++]=queue[start]->left;
            if(queue[start]->right) 
            queue[end++]=queue[start]->right;
            start++;
        }
    }
}

int finddepth(struct Tree* root)
{
    if(!root) return 0;
    int leftdepth=finddepth(root->left);
    int rightdepth=finddepth(root->right);
    return (leftdepth>rightdepth?leftdepth:rightdepth)+1;
}

struct Tree *build(int* preOrder,int* inOrder,int start,int end,int *ptr)
{
    if(start>end) return  NULL;
    struct Tree *root=malloc(sizeof(struct Tree));
    int index=start;
    while(inOrder[index]!=preOrder[(*ptr)])  index++;
    root->val=preOrder[(*ptr)++];
    root->left=build(preOrder,inOrder,start,index-1,ptr);
    root->right=build(preOrder,inOrder,index+1,end,ptr);
    return root;
}

int** levelOrder(struct Tree* root, int* returnSize, int** returnColumnSizes ) {
    if(!root) return NULL;
    *returnSize=finddepth(root);
    int** arr=malloc(*returnSize*(sizeof(int*)));
    *returnColumnSizes=malloc(*returnSize*sizeof(int));
    struct Tree* queue[1500]={root};
    resort(returnSize,returnColumnSizes,arr,queue);
    return arr;
}

int* solve(int* preOrder, int preOrderLen, int* inOrder, int inOrderLen, int* returnSize ) {
    int start=0,end=inOrderLen-1,ptr=0;
    int* returnColumnSizes,**arr;
    struct Tree *root=build(preOrder, inOrder,start,end,&ptr);
    arr=levelOrder(root, returnSize, &returnColumnSizes);
    int *result=malloc(*returnSize*sizeof(int));
    for(int i=0;i<*returnSize;i++)
        result[i]=arr[i][(returnColumnSizes)[i]-1];
    free(returnColumnSizes);
    return result;
}