8-3 C. 先序+中序还原二叉树

题目描述

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入

输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输入样例：

9
ABDFGHIEC
FDHGIBEAC

输出

输出为一个整数，即该二叉树的高度。

输出样例：

5

代码

#include <iostream>
using namespace std;
 
struct Node{
    char data;
    Node *left;
    Node *right;
};
 
class Tree{
public:
    int len,i=-1,flag=0;
    string pre,mid;
    Node *root;
    Tree(){
        cin >> len >> pre >> mid;
    }
 
    Node *create(int l, int r){  //建树,根据中序序列界定左右边界
        Node *t = new Node;
        if(flag == 0){  //记录根结点
            root = t;
            flag = 1;
        }
        i++;
        t->data = pre[i];  //根据先序序列依次处理结点
        t->left = NULL;  //要初始化NULL，高度计算时必要
        t->right = NULL;
        if(l == r){
            return t;
        }
        int n = toFind(pre[i]);  //确定这一字符在中序中的位置，以便将两侧其余结点分左右子树
        t->left = create(l,n-1);
        t->right = create(n+1,r);
        return t;
    }
 
    int toFind(char c){
        for(int k = 0; k < len; k++){
            if(c == mid[k]){
                return k;
            }
        }
        return -1;
    }
 
    int height(Node *t){
        if(t == NULL){
            return 0;
        }else if(t->left == NULL && t->right == NULL) {
            return 1;
        }
        int lheight = height(t->left);
        int rheight = height(t->right);
        if(lheight > rheight){
            return lheight+1;
        }else{
            return rheight+1;
        }
    }
};
 
int main()
{
    Tree tree;
    tree.create(0,tree.len-1);
    int res = tree.height(tree.root);
    cout << res;
    return 0;
}