列表

详情

KS2. 将满二叉树转换为求和树

描述

给出满二叉树的前序遍历结果和中序遍历结果，编写算法将其转化为求和树

什么是求和树：二叉树的求和树， 是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。

二叉树：

求和树：


二叉树给出前序和中序输入，求和树要求中序输出；
所有处理数据不会大于int；

数据范围：二叉树的节点数满足 ,节点上的值满足

输入描述

2行整数，第1行表示二叉树的前序遍历，第2行表示二叉树的中序遍历，以空格分割

输出描述

1行整数，表示求和树的中序遍历，以空格分割

示例1

输入: 

10 -2 8 -4 6 7 5
8 -2 -4 10 7 6 5

输出: 

0 4 0 20 0 12 0

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 228KB, 提交时间: 2019-12-10 

#include<stdio.h>
#include<stdlib.h>
#define M 100000000
typedef struct binode
{
    int data1;
    int data2;
    struct binode *lc,*rc;
}binode,*bitree;
  
void createBitree(bitree *r,int *d,int low,int high)
{
    if(high<low)
    {
        *r = NULL;
        return;
    }
    int mid;
    mid = (low+high)/2;
    (*r) = (bitree)malloc(sizeof(struct binode));
    (*r)->data1 = d[mid];
    createBitree(&(*r)->lc,d,low,mid-1);
    createBitree(&(*r)->rc,d,mid+1,high);
    return;
}
void sum(bitree *r)
{
    if((*r)->lc==NULL)
    {
        (*r)->data2=0;
        return;
    }
    else
    {
        sum(&(*r)->lc);
        sum(&(*r)->rc);
        (*r)->data2 = (*r)->lc->data2+(*r)->lc->data1+(*r)->rc->data2+(*r)->rc->data1;
    }
    return;
}
void printMid(bitree r)
{
    if(r==NULL)
        return;
    else{
        printMid(r->lc);
        printf("%d ",r->data2);
        printMid(r->rc);
    }
    return;
}
  
int main()
{
    bitree r = NULL;
    int data[M];
    int n=1;
    do
    {
        scanf("%d",&n);
    }while(getchar()!='\n');
      
    n=1;
    do{
        scanf("%d",&data[n]);
        n++;
    }while(getchar()!='\n');
    n--;
      
    createBitree(&r,data,1,n);
    sum(&r);
    printMid(r);
      
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 304KB, 提交时间: 2019-12-10 

#include<stdio.h>
#include<stdlib.h>
#define M 100000000
typedef struct binode
{
    int data1;
    int data2;
    struct binode *lc,*rc;
}binode,*bitree;
 
void createBitree(bitree *r,int *d,int low,int high)
{
    if(high<low)
    {
        *r = NULL;
        return;
    }
    int mid;
    mid = (low+high)/2;
    (*r) = (bitree)malloc(sizeof(struct binode));
    (*r)->data1 = d[mid];
    createBitree(&(*r)->lc,d,low,mid-1);
    createBitree(&(*r)->rc,d,mid+1,high);
    return;
}
void sum(bitree *r)
{
    if((*r)->lc==NULL)
    {
        (*r)->data2=0;
        return;
    }
    else
    {
        sum(&(*r)->lc);
        sum(&(*r)->rc);
        (*r)->data2 = (*r)->lc->data2+(*r)->lc->data1+(*r)->rc->data2+(*r)->rc->data1;
    }
    return;
}
void printMid(bitree r)
{
    if(r==NULL)
        return;
    else{
        printMid(r->lc);
        printf("%d ",r->data2);
        printMid(r->rc);
    }
    return;
}
 
int main()
{
    bitree r = NULL;
    int data[M];
    int n=1;
    do
    {
        scanf("%d",&n);
    }while(getchar()!='\n');
     
    n=1;
    do{
        scanf("%d",&data[n]);
        n++;
    }while(getchar()!='\n');
    n--;
     
    createBitree(&r,data,1,n);
    sum(&r);
    printMid(r);
     
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2019-12-11 

#include<stdio.h>
#include<stdlib.h>
#define M 100000000
typedef struct binode
{
    int data1;
    int data2;
    struct binode *lc,*rc;
}binode,*bitree;
   
void createBitree(bitree *r,int *d,int low,int high)
{
    if(high<low)
    {
        *r = NULL;
        return;
    }
    int mid;
    mid = (low+high)/2;
    (*r) = (bitree)malloc(sizeof(struct binode));
    (*r)->data1 = d[mid];
    createBitree(&(*r)->lc,d,low,mid-1);
    createBitree(&(*r)->rc,d,mid+1,high);
    return;
}
void sum(bitree *r)
{
    if((*r)->lc==NULL)
    {
        (*r)->data2=0;
        return;
    }
    else
    {
        sum(&(*r)->lc);
        sum(&(*r)->rc);
        (*r)->data2 = (*r)->lc->data2+(*r)->lc->data1+(*r)->rc->data2+(*r)->rc->data1;
    }
    return;
}
void printMid(bitree r)
{
    if(r==NULL)
        return;
    else{
        printMid(r->lc);
        printf("%d ",r->data2);
        printMid(r->rc);
    }
    return;
}
   
int main()
{
    bitree r = NULL;
    int data[M];
    int n=1;
    do
    {
        scanf("%d",&n);
    }while(getchar()!='\n');
       
    n=1;
    do{
        scanf("%d",&data[n]);
        n++;
    }while(getchar()!='\n');
    n--;
       
    createBitree(&r,data,1,n);
    sum(&r);
    printMid(r);
       
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2020-11-03 

#include<stdio.h>
#include<math.h>
int main()
{
    int mi(int x,int y);
    int qian[1000]={0},zhong[1000]={0},sum[1000]={0};
    int num=1;
    scanf("%d",&qian[num]);
    while(getchar()!='\n')
    {
        num++;
        scanf("%d",&qian[num]);
    }
    for(int i=1;i<num;i++)
    {
        scanf("%d ",&zhong[i]);
    }
    scanf("%d",&zhong[num]);
    for(int i=1;i<=num;i+=2)//叶子节点都为０
    {
        sum[i]=0;
    }
    for(int j=2;j<num;j+=4)//第一层
    {
        sum[j]=zhong[j-1]+zhong[j+1];
    }
    for(int i=2;i<=sqrt(num+1);i++)//层数
    {
        //printf("%d\n",i);
        for(int j=mi(2,i);j<num;j+=mi(2,i+1))
        {
            sum[j]=sum[j-mi(2,i-1)]+sum[j+mi(2,i-1)]+zhong[j-mi(2,i-1)]+zhong[j+mi(2,i-1)];
        }
    }

    for(int i=1;i<num;i++)
    {
        printf("%d ",sum[i]);
    }
    printf("%d\n",sum[num]);
    return 0;
}
int mi(int x,int y)
{
    int ans=1;
    for(int i=0;i<y;i++)
    {
        ans = ans*x;
    }
    return ans;
}

C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2020-04-10 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100

typedef struct tree_node{
    int data;
    struct tree_node *left;
    struct tree_node *right;
}tree_node_type;

void reconstruct_bitree(int *preorder, int *inorder, tree_node_type *root, int length){
    int i;

    if(length == 1){
        root->data = preorder[0];
        root->left = NULL;
        root->right = NULL;
    }else{
        root->data = preorder[0];

        int preorder_left[N] = {0}, preorder_right[N] = {0};
        int inorder_left[N] = {0}, inorder_right[N] = {0};
        // divide in-order strings
        for(i=0;i<length;i++){
            if(inorder[i] == preorder[0])
                break;
        }
        int lin_left, lin_right;
        lin_left = i;
        lin_right = length-i-1;

        memcpy(inorder_left,inorder,sizeof(int)*lin_left);
        memcpy(inorder_right,inorder+i+1,sizeof(int)*lin_right);
        // divide pre-order strings

        memcpy(preorder_left,preorder+1,sizeof(int)*lin_left);
        memcpy(preorder_right,preorder+1+lin_left,sizeof(int)*lin_right);

        // reconstruct binary tree recursively
        if (lin_left > 0){
            tree_node_type *root_left;
            root_left = (tree_node_type*)malloc(sizeof(tree_node_type));
            reconstruct_bitree(preorder_left,inorder_left,root_left,lin_left);
            root->left = root_left;
        }else{
            root->left = NULL;
        }

        if (lin_right > 0){
            tree_node_type *root_right;
            root_right = (tree_node_type*)malloc(sizeof(tree_node_type));
            reconstruct_bitree(preorder_right,inorder_right,root_right,lin_right);
            root->right = root_right;
        }else{
            root->right = NULL;
        }
    }
}

void print_tree_pre(tree_node_type *root){
    if(root != NULL){
        printf("%d ",root->data);
        if(root->left != NULL){
            print_tree_pre(root->left);
        }
        if(root->right != NULL){
            print_tree_pre(root->right);
        }
    }
}

void print_tree_in(tree_node_type *root){
    if(root != NULL){
        if(root->left != NULL){
            print_tree_in(root->left);
        }
        printf("%d ",root->data);
        if(root->right != NULL){
            print_tree_in(root->right);
        }
    }
}

void print_tree_pos(tree_node_type *root){
    if(root != NULL){
        if(root->left != NULL){
            print_tree_pos(root->left);
        }
        if(root->right != NULL){
            print_tree_pos(root->right);
        }
        printf("%d ",root->data);
    }
}

int sum_bitree(tree_node_type *root){
    int sum = 0;
    
    if(root->left != NULL){
        sum = sum + sum_bitree(root->left);
    }
    if(root->right != NULL){
        sum = sum + sum_bitree(root->right);
    }
    int temp;
    temp = root->data;
    root->data = sum;
    return temp + sum;
}

int main()
{
    int preorder[N] = {0};
    int inorder[N] = {0};
    int i,Len;
    char s;
    for(i=0;(i<N)&&(s!='\n');i++){
        scanf("%d",&preorder[i]);
        s = getchar();
    }
    Len = i;
    s = '\0';
    for(i=0;(i<N)&&(s!='\n');i++){
        scanf("%d",&inorder[i]);
        s = getchar();
    }

    tree_node_type *bitree_root;
    bitree_root = (tree_node_type*)malloc(sizeof(tree_node_type));

    reconstruct_bitree(preorder,inorder,bitree_root,Len);
    
    //tree_node_type *sum_bitree_root;
    //sum_bitree_root = (tree_node_type*)malloc(sizeof(tree_node_type));
    
    //memcpy(sum_bitree_root,bitree_root,sizeof(tree_node_type));
    
    int sum;
    sum = sum_bitree(bitree_root);

    //printf("Binary tree with pre-order: \n");
    //print_tree_pre(bitree_root);
    //putchar('\n');

    //printf("Binary tree with in-order: \n");
    //print_tree_in(bitree_root);
    //putchar('\n');

    //printf("Binary tree with past-order: \n");
    //print_tree_pos(bitree_root);
    //putchar('\n');
    
    //printf("Sum binary tree with in-order:\n");
    print_tree_in(bitree_root);
    
    return 0;
}

上一题

© 2024 nowcoder.com