UVA 536 二叉树重建（递归建立二叉树模板）

待我称王封你为后i 2022-05-31 12:35 160阅读 0赞

![20180224222704169][]![20180224222710500][]

题目解析：

题目很简单就是一个简单的数据结构，二叉树的递归建立，给出二叉树的先序遍历和中序遍历，让我们输出后续遍历，直接模拟一下就可以了，很水，1A

代码：

#include <bits/stdc++.h>
    using namespace std;
    struct Node
    {
        char c;
        Node *left;
        Node *right;
    };
    Node* buildNode(char c)
    {
        Node* node = (Node*)malloc(sizeof(Node));
        node->c = c;
        node->left = node->right = NULL;
        return node;
    }
    Node* rebuildTree(char *pre,char *in,int len)
    {
        int i=0;
        if(len==0)
            return NULL;
        Node *head = buildNode(pre[0]);
        for(i=0; i<len; i++)
        {
            if(in[i]==pre[0])
                break;
        }
        head->left = rebuildTree(pre+1,in,i);
        head->right = rebuildTree(pre+i+1,in+i+1,len-i-1);
        return head;
    }
    void postorder(Node *head)
    {
        if(head==NULL)
            return;
        postorder(head->left);
        postorder(head->right);
        cout<<head->c;
    }
    int  main()
    {
        //freopen("in.txt","r",stdin);
        char in[1000],pre[1000];
        while(scanf("%s%s",pre,in)!=EOF)
        {
            postorder(rebuildTree(pre,in,strlen(pre)));
            printf("\n");
        }
        return 0;
    }

[20180224222704169]: https://img-blog.csdn.net/20180224222704169
[20180224222710500]: /images/20220531/31bad0f8e8824e378c054af28a0f128b.png

发表评论取消回复

表情：

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

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

相关阅读

相关 UVA 536 Tree Recovery 二叉树重建（重建二叉树+DFS）

本题起初采用的是二叉树重建+dfs完成，然后看见网上不用建树也可以完成，也尝试了这种方法通过中序遍历和先序遍历（或后序遍历）可以重建二叉树，AC代码如下：二叉树重建+D

一时失言乱红尘/ 2024年02月17日 19:05/ 0 赞/ 31 阅读

相关 UVA 536 二叉树重建（递归建立二叉树模板）

![20180224222704169][]![20180224222710500][] 题目解析：题目很简单就是一个简单的数据结构，二叉树的递归建立，给出二叉树的先序遍

待我称王封你为后i/ 2022年05月31日 12:35/ 0 赞/ 161 阅读

相关二叉树应用_重建二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8

喜欢ヅ旅行/ 2022年05月22日 02:37/ 0 赞/ 198 阅读

相关重建二叉树

重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。如前序\{1,2,4,7,3,5,6,8

亦凉/ 2022年04月24日 13:54/ 0 赞/ 162 阅读

相关用递归方法建立二叉树

分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangju

绝地灬酷狼/ 2022年04月22日 06:28/ 0 赞/ 117 阅读

相关重建二叉树

/ Definition for binary tree struct TreeNode { int val;

灰太狼/ 2022年04月03日 13:44/ 0 赞/ 215 阅读

相关重建二叉树

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=1][h

曾经终败给现在/ 2022年03月20日 02:46/ 0 赞/ 149 阅读

相关重建二叉树

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6

古城微笑少年丶/ 2022年03月06日 12:26/ 0 赞/ 196 阅读

相关重建二叉树

　　直接上代码了 struct BTNode { int val; BTNode lchild; BTNode rch

逃离我推掉我的手/ 2022年01月05日 10:39/ 0 赞/ 225 阅读

相关二叉树重建

给定二叉树的先序遍历序列和中序遍历序列，进行二叉树的重建以及后序遍历队列。突然看到这个问题。。发现之前的想法都忘记了=\_=||，果然算法题一日不写手生啊，还是得好好坚持

淡淡的烟草味﹌/ 2021年12月14日 04:15/ 0 赞/ 247 阅读