HDU 1710 Binary Tree Traversals(二叉树)

题目地址:HDU 1710

已知二叉树先序和中序求后序。

#include <stdio.h>
#include <string.h>
int a[1001], cnt;
typedef struct node
{
    int date ;
    node *lchild , *rchild ;
}*tree;
int getk(int ch,int ino[],int is,int n)
{
    for(int i = is ; i <= is + n -1 ; i++)
        if(ino[i]==ch)return i;
}
void gettree(tree &t,int pre[],int ino[],int ps,int is,int n)
{
    if(n==0) t = NULL;
    else
    {
        t = new node;
        t->date = pre[ps];
        int k = getk(pre[ps],ino,is,n);
        if(k == is) t->lchild = NULL;
        else
            gettree(t->lchild,pre,ino,ps+1,is,k-is);
        if(k == is+n-1) t->rchild = NULL;
        else
            gettree(t->rchild,pre,ino,ps+1+(k-is),k+1,n-1-(k-is));
    }
}
void pritree1(tree t)
{
    if(t)
    {
        pritree1(t->lchild);
        pritree1(t->rchild);
        a[cnt++]=t->date;
    }
}
int main()
{
    int i, n, t;
    int pre[1001] , ino[1001] ;
    while(scanf("%d", &n)!=EOF)
    {
        cnt=0;
        tree head;
        for(i=0; i<n; i++)
        {
            scanf("%d",&pre[i]);
        }
        for(i=0; i<n; i++)
        {
            scanf("%d",&ino[i]);
        }
        gettree(head,pre,ino,0,0,n);
        pritree1(head);
        for(i=0; i<cnt-1; i++)
            printf("%d ",a[i]);
        printf("%d\n",a[cnt-1]);
    }
    return 0;
}
时间: 04-24

HDU 1710 Binary Tree Traversals(二叉树)的相关文章

hdu 1710 Binary Tree Traversals 前序遍历和中序推后序

题链;http://acm.hdu.edu.cn/showproblem.php?pid=1710 Binary Tree Traversals Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4205    Accepted Submission(s): 1904 Problem Description A binary tree i

【二叉树】hdu 1710 Binary Tree Traversals

acm.hdu.edu.cn/showproblem.php?pid=1710 [题意] 给定一棵二叉树的前序遍历和中序遍历,输出后序遍历 [思路] 根据前序遍历和中序遍历递归建树,再后续遍历输出 malloc申请空间在堆,函数返回,内存不释放,需要free手动释放 [Accepted] #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<alg

HDU 1710 Binary Tree Traversals

题意:给出一颗二叉树的前序遍历和中序遍历,输出其后续遍历 首先知道中序遍历是左子树根右子树递归遍历的,所以只要找到根节点,就能够拆分出左右子树 前序遍历是按照根左子树右子树递归遍历的,那么可以找出这颗树的根节点, 然后拆分出左右子树,对左右子树进行相同的操作,也就是将建树的这个函数递归调用下去 build函数还是理解了好久啊话说= =仍然是学习的代码 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring>

hdu 1701 (Binary Tree Traversals)(二叉树前序中序推后序)

Binary Tree Traversals Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Description A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called

hdu1710(Binary Tree Traversals)(二叉树遍历)

Binary Tree Traversals Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3475    Accepted Submission(s): 1555 Problem Description A binary tree is a finite set of vertices that is either empty or

HDOJ 题目1710 Binary Tree Traversals(二叉搜索树)

Binary Tree Traversals Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3912    Accepted Submission(s): 1741 Problem Description A binary tree is a finite set of vertices that is either empty or

hdu1710 Binary Tree Traversals(二叉树的遍历)

A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically

HDU 1710 二叉树的遍历 Binary Tree Traversals

Binary Tree Traversals Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4330    Accepted Submission(s): 1970 Problem Description A binary tree is a finite set of vertices that is either empty or

HDU-1701 Binary Tree Traversals

http://acm.hdu.edu.cn/showproblem.php?pid=1710 已知先序和中序遍历,求后序遍历二叉树. 思路:先递归建树的过程,后后序遍历. Binary Tree Traversals Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3442    Accepted Submission(s): 1541