14287: 【原4287】重建二叉树

题目

题目描述

author: jianglin huang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4287

Description

小助教很喜欢玩二叉树的游戏，特别是构建节点为大写字母的二叉树，为了将他构建的二叉树保存下来，他为每棵树写下了其前序遍历和中序遍历的结果。他认为有了这棵树前序和中序遍历的信息，他以后就可以重建这棵树了。你能帮小助教的这个想法变为现实吗？

Input Format

第1行：两个字符串，分别为二叉树前序遍历结果和中序遍历结果

Output Format

第1行：一个字符串，重建的二叉树后序遍历的结果

Sample Input1

DBACEGF ABCDEFG

Sample Output1

ACBFGED

Sample Input2

BCAD CBAD

Sample Output2

CDAB

Zsi-r's solution

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

void post(const char tree[],int address)
{
    if (address >= strlen(tree))
        return;
    if (tree[address]=='@')
        return;
    post(tree, address * 2);
    post(tree, address * 2 + 1);
    cout << tree[address];
}

void f(int root , int start ,int end,int count,char tree[],const char pre[],const char mid[]){
    int i;
    if (end < start)
        return; 
    else
    {
        tree[count] = pre[root];
    }


    for (i = start; i <= end;i++)
        if (mid[i]==pre[root])
            break;
    f(root + 1, start, i - 1, 2 * count, tree, pre, mid);
    f(root + 1 + i - start, i + 1, end, 2 * count + 1, tree, pre, mid);
}

int main()
{
    char pre[100], mid[100];
    char tree[1000001];

    cin >> pre;
    cin >> mid;
    int len = strlen(pre);
    for (int k = 0; k<1000000 ;k++)
    {
        tree[k] = '@';
    }

    f(0, 0, len - 1, 1, tree, pre, mid);

    /*
    int num = 0, i = 1;
    while (num!=len)
    {
        if (tree[i]=='@')
            cout << "NULL" << ' ';
        else{
            cout << tree[i] << ' ';
            num++;
        }
        i++;
    }
    */

    post(tree, 1);

    return 0;
}