超时了,求助
查看原帖
超时了,求助
783010
lpl2002楼主2023/5/4 19:39
#include <stdio.h>
#include <stdlib.h>

typedef struct treeNode
{
    char ch;
    struct treeNode *lChild;
    struct treeNode *rChild;
} treeNode;

void creatTree(treeNode *p, char *a, char *b, int af, int ae, int bf, int be)
{
    p->ch = b[bf];
    int root;
    for (root = 0; root <= ae; root++)
        if (a[root] == b[bf])
            break;

    if (root - af != 0)
    {
        p->lChild = (treeNode *)malloc(sizeof(treeNode));
        p->lChild->lChild = NULL;
        p->lChild->rChild = NULL;
        creatTree(p->lChild, a, b, af, root - 1, bf + 1, bf + root - af);
    }
    if (root - ae != 0)
    {
        p->rChild = (treeNode *)malloc(sizeof(treeNode));
        p->rChild->lChild = NULL;
        p->rChild->rChild = NULL;
        creatTree(p->rChild, a, b, root + 1, ae, bf + root - af + 1, be);
    }
}

// 后序遍历树
void postOrderTraverse(treeNode *p)
{
    if (p->lChild != NULL)
        postOrderTraverse(p->lChild);

    if (p->rChild != NULL)
        postOrderTraverse(p->rChild);

    printf("%c", p->ch);
}

int main()
{
    char a[100005]; // 中序
    char b[100005]; // 前序
    int i = 0;
    int j = 0;
    char ch;
    while ((ch = getchar()) != '\r')
    {
        if (ch > 'Z' || ch < 'A')
            continue;
        a[i] = ch;
        i++;
    }
    ch = getchar();
    while ((ch = getchar()) != '\r')
    {
        if (ch > 'Z' || ch < 'A')
            continue;
        b[j] = ch;
        j++;
    }
    treeNode *p = (treeNode *)malloc(sizeof(treeNode));
    p->lChild = NULL;
    p->rChild = NULL;
    creatTree(p, a, b, 0, i - 1, 0, j - 1);
    postOrderTraverse(p);
}
2023/5/4 19:39
加载中...