题目描述
7-23 还原二叉树 (25分)
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

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

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

输入样例:
9
ABDFGHIEC
FDHGIBEAC
输出样例:
5
思路：先利用二叉树的前序遍历和后序遍历构造出二叉树，再利用层序遍历统计树的高度。
AC代码

# include <bits/stdc++.h>using namespace std;struct Node
{char data;Node* left;Node* right;Node(char c):data(c), left(NULL), right(NULL){}
};char *pre, *in;
int N, ans = 0;Node* create(int s1, int s2, int len)
{if (len == 0) return NULL;Node* root = new Node(pre[s1]);int llen = 0;for (int i = s2; i < s2 + len; ++i){if (in[i] == pre[s1]) break;++llen;}root->left = create(s1+1, s2, llen);root->right = create(s1+llen+1, s2+llen+1, len - llen -1);return root;
}void floorOrder(Node* root)
{queue<Node*> q;if (root == NULL) return;q.push(root);while (!q.empty()){++ans;queue<Node*> tmp;while (!q.empty()){if (q.front()->left) tmp.push(q.front()->left);if (q.front()->right) tmp.push(q.front()->right);q.pop();}while (!tmp.empty()){q.push(tmp.front());tmp.pop();}}
}int main()
{cin>>N;pre = new char[N];in = new char[N];for (int i = 0; i < N; ++i){cin>>pre[i];}for (int i = 0; i < N; ++i){cin>>in[i];}floorOrder(create(0, 0, N));cout<<ans;delete[] pre;delete[] in;return 0;
}