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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求二叉树的右视图
 * @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
    if(!preOrder || !inOrder) {*returnSize = 0; return NULL;}

    struct TreeNode *pTN_stk[preOrderLen];
    int idx = 0, i = 1, j = 0, top, cmp;
    struct TreeNode *Header = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
    struct TreeNode *pHead = Header;
    pHead->val = top = preOrder[0];
    cmp = inOrder[0];
    pTN_stk[0] = pHead;
    while(i < preOrderLen) {
        if(top != cmp) {
            pHead->left = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
            pHead = pHead->left;
            pHead->val = top = preOrder[i++];
            pTN_stk[++idx] = pHead;
            continue;
        }
        j++;
        while(--idx != -1 && pTN_stk[idx]->val == inOrder[j]) {
            pHead = pTN_stk[idx];
            j++;
        }
        pHead->right = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
        pHead = pHead->right;
        pHead->val = top = preOrder[i++];
        cmp = inOrder[j];
        pTN_stk[++idx] = pHead;
    }

    int f_idx = 0, rear_idx = 0, record[preOrderLen], id = 0;
    pTN_stk[0] = Header;
    idx = 0;
    while(idx <= rear_idx) {
        while(idx < f_idx) {
            pHead = pTN_stk[idx++];
            if(pHead->left) pTN_stk[++rear_idx] = pHead->left;
            if(pHead->right) pTN_stk[++rear_idx] = pHead->right;
            free(pHead);
        }
        pHead = pTN_stk[idx++];
        if(pHead->left) pTN_stk[++rear_idx] = pHead->left;
        if(pHead->right) pTN_stk[++rear_idx] = pHead->right;
        record[id++] = pHead->val;
        free(pHead);
        f_idx = rear_idx;
    }

    int *res = (int*)malloc(id * sizeof(int));
    memcpy(res, record, id*sizeof(int));
    *returnSize = id;
    return res;
}