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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param xianxuLen int xianxu数组长度
 * @param zhongxu int整型一维数组 中序遍历
 * @param zhongxuLen int zhongxu数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
struct TreeNode* reConstructBinaryTree(int* pre, int preLen, int* vin, int vinLen ) {
    // write code here
    if(preLen==0 || vinLen==0){
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    int i = 0, j = 0;
    while(pre[0] != vin[i]){
        i++;
    }
    
    root->val = pre[0];
    int newleftpre[i+1],newleftvin[i+1],newrightpre[preLen-i],newrightvin[preLen-i];
    while(j < i){
        newleftpre[j] = pre[j+1];
        newleftvin[j] = vin[j];
        j++;
    }
    j = 0;
    while(i+j+1 < preLen){
        newrightpre[j] = pre[i+j+1];
        newrightvin[j] = vin[i+j+1];
        j++;
    }
    root->left = reConstructBinaryTree(newleftpre,i,newleftvin,i);
    root->right = reConstructBinaryTree(newrightpre,preLen-i-1,newrightvin,preLen-i-1);
    
    return root;
    
}
int* solve(int* xianxu, int xianxuLen, int* zhongxu, int zhongxuLen, int* returnSize ) {
    // write code here
    struct TreeNode* root = reConstructBinaryTree(xianxu,xianxuLen,zhongxu,zhongxuLen);
    if(root == NULL){
        return NULL;
    }
    *returnSize = 0;
    int* ret = (int*)malloc(sizeof(int)*10001);
    struct TreeNode* queue[10001];
    int head = 0, tail = 0;
    queue[tail++] = root;
    
    while(head != tail){
        int curtail = tail;
        struct TreeNode* p = queue[curtail-1];
        ret[(*returnSize)++] = p->val;
        while(head < curtail){
            struct TreeNode* p = queue[head];
            if(p->left){
                queue[tail++] = p->left;
            }
            if(p->right){
                queue[tail++] = p->right;
            }
            head++;
        }
    }
    return ret;
}