求二叉树的先序遍历

╰半夏微凉° 2022-07-12 07:08 149阅读 0赞

Problem Description

已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历  
Input

输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的中序遍历序列，第二个字符串表示二叉树的后序遍历序列。  
Output

输出二叉树的先序遍历序列  
Example Input

2  
dbgeafc  
dgebfca  
lnixu  
linux  
Example Output

abdegcf  
xnliu  
Hint

Author

GYX

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    struct node
    {
        int data;
        struct node *l, *r;
    };
    struct node *creat(int n, char *a, char *b)
    {
        int i;
        struct node *root;
        if(n == 0) return NULL;//第二次忘了空节点。。。
        root = (struct node *) malloc(sizeof(struct node));//要给root分配空间，第一次忘了。。。
        root -> data = b[n-1];
        for(i = 0; i < n; i++)
        {
            if(a[i] == b[n-1])
                break;
        }
        printf("%c", root -> data);
        root -> l = creat(i, a, b);
        root -> r = creat(n - i - 1, a + i + 1, b + i);
        return root;
    };
    int main()
    {
        int t;
        scanf("%d", &t);
        char a[55], b[55];
        while(t--)
        {
            scanf("%s%s", a, b);
            int n = strlen(a);
            creat(n, a, b);
            printf("\n");
        }
        return 0;
    }

**先序中序后序知道两个可以求另外一个了，就是有的判断别忘了，感觉有点灵性了。**

发表评论取消回复

表情：

评论列表（有 0 条评论，149人围观）

还没有评论，来说两句吧...

相关阅读

相关求二叉树的先序遍历

求二叉树的先序遍历 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Prob

亦凉/ 2024年02月18日 22:31/ 0 赞/ 25 阅读

相关求二叉树的先序遍历

求二叉树的先序遍历 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述已知一棵二叉树的

柔光的暖阳◎/ 2022年08月18日 02:25/ 0 赞/ 126 阅读

相关已知二叉树先序遍历中序遍历求其后序遍历、重建二叉树

已知二叉树先序遍历中序遍历求其后序遍历 (注：已知中序遍历序列和剩下两种遍历序列中的一种都可以确定二叉树，即可得到另一种遍历序列，但是已知前序遍历和后

水深无声/ 2022年08月09日 01:53/ 0 赞/ 172 阅读

相关求二叉树的先序遍历

Problem Description 已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历 Input 输入数据有多组，第一行是一个整数t (t<1000)，代表有

╰半夏微凉°/ 2022年07月12日 07:08/ 0 赞/ 150 阅读

相关求二叉树的先序遍历

Problem Description 已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历 Input 输入数据有多组，第一行是一个整数t (t<1000)

素颜马尾好姑娘i/ 2022年07月12日 02:10/ 0 赞/ 137 阅读

相关二叉树先序遍历

前两天面试，看见了个笔试题，关于二叉树的，今天算是把自己的一点理解写下来吧。今天看网文，才想起来，二叉树的先序遍历、中序遍历、后序遍历，遍历顺序都是

向右看齐/ 2022年07月10日 10:57/ 0 赞/ 189 阅读

相关二叉树先序遍历中序遍历建立二叉树然后后序遍历

题目描述二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左

男娘i/ 2022年06月01日 07:24/ 0 赞/ 246 阅读

相关二叉树先序遍历

下面是leetcode上的一道题，先序遍历二叉树。 Given a binary tree, return the preorder traversal of its nod

爱被打了一巴掌/ 2022年05月16日 12:52/ 0 赞/ 186 阅读

相关求二叉树的先序遍历

Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description 已

╰+攻爆jí腚メ/ 2022年05月14日 03:40/ 0 赞/ 126 阅读

相关二叉树之先序遍历

　　二叉树不同于列表、链表、栈、队列这些线性结构，也不同于图这种非线性结构，它属于半线性结构。我们在搞二叉树的时候不要从轮子造起，而要善于引用此前的工作成果，转化成以前已经玩烂

墨蓝/ 2021年11月09日 00:32/ 0 赞/ 288 阅读