[数据结构与算法]重建二叉树

题目：

重建二叉树

给定二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根序列，最后删除该二叉树；如给定的中根和后根序列不合法，则亦能识别。

输入格式

输入为两行字符串，第一行表示某二叉树的后根序列，第二行表示其中根序列。结点的值均为A-Z的大写字母，故二叉树结点个数不超过26，且保证输入的两个序列都是结点的全排列，但不一定是合法的中根和后根序列。

输出格式

如果输入的序列不合法（不是同一棵树的中根序列和后根序列），则输出INVALID。若输入序列合法，输出为两行，第一行为一个整数，表示该二叉树的高度，第二行为一个字符串，表示该二叉树的先根序列。

输入样例1：

CEFDBHGA
CBEDFAGH 

输出样例1：

3
ABCDEFGH

输入样例2：

CBEDFAGH
CEFDBHGA 

输出样例2：

INVALID

输入样例3：

BCA 
CAB

输出样例3：

INVALID

代码：

#include <iostream>
#include <stdio.h>
using namespace std;

struct Tree {
    char item;
    Tree* L = NULL;
    Tree* R = NULL;
};

string postorder;
string inorder;
int istree = 1;


int high(Tree* t) {
    if (t == NULL) return -1;
    int leftvalue = high(t->L);
    int rightvalue = high(t->R);
    if (leftvalue > rightvalue) return leftvalue + 1;
    return rightvalue + 1;
}

void preorder_travel(Tree* t) {
    if (t == NULL) return;
    cout << t->item;
    preorder_travel(t->L);
    preorder_travel(t->R);
}

void creattree(Tree*& t, int len, int poststart, int instart)
{
    int pos = 0;
    int flag = 0;
   
    int inend = instart + len;
    int postend = poststart + len;

    for (pos = instart; pos < inend; pos++)
        if (inorder[pos] == postorder[postend - 1]) {
            flag = 1;
            break;
        }
   
    int leftlen = pos - instart;
    int rightlen = len - pos - 1 + instart;
    if (flag) {
        t = new Tree;
        t->item = inorder[pos];
        if (leftlen > 0)
            creattree(t->L, leftlen, poststart, instart);
        if (rightlen > 0)
            creattree(t->R, rightlen, poststart + pos - instart, pos + 1);
    }
    else
        istree = 0;
}

int main()
{
    cin >> postorder >> inorder;
    int inlen = inorder.size();
    Tree* root;
    root = new Tree;
    creattree(root, inlen, 0, 0);
    if (istree == 0) cout << "INVALID";
    else {
        cout << high(root) << endl;
        preorder_travel(root);
    }
    return 0;
}