P4738 二叉树问题（提高）

解题思路

题目给出了一棵二叉树的先序遍历序列和中序遍历序列（每个字母代表一个结点，不重复，区分大小写），要求算出这棵树的高度。输入可能有多组测试数据，要一直读到文件结束。

先序遍历的第一个字符一定是整棵树的根结点。我们再到中序遍历序列里找到这个根的位置，根据中序遍历的性质，根左边的所有字符就是左子树的结点，根右边的所有字符就是右子树的结点。同时，在先序遍历里，紧跟根后面的那一段（长度正好等于左子树的结点个数）就是左子树的先序序列，剩下的一段就是右子树的先序序列。这样左右子树的先序、中序序列都有了，就可以递归地处理左右子树，再求出它们的高度。

具体实现时，写一个递归函数 height(pl,pr,il,ir)，表示用先序的 [pl,pr] 段和中序的 [il,ir] 段来构造子树并返回它的高度。如果区间为空（pl>pr），说明是空子树，高度为 0；否则在中序 [il,ir] 里找到根的位置 k，左子树的结点个数是 k-il，于是左子树的先序区间是 [pl+1, pl+(k-il)]，右子树的先序区间是 [pl+(k-il)+1, pr]，分别递归求出左右子树的高度，取较大者再加上 1（根结点自己算一层），就是整棵树的高度。以样例为例：先序 ABDFGHIEC、中序 FDHGIBEAC，根 A 的左子树有 7 个结点、高度 4，右子树只有 C、高度 1，所以整棵树高度 5。N 不超过 50，递归深度最多 50，不会栈溢出。

参考代码

// 二叉树问题：已知先序和中序遍历序列，求二叉树的高度（多组测试数据）
#include <cstdio>
char pre[55], in[55];   // 先序、中序序列
int height(int pl,int pr,int il,int ir){
  int k,h1,h2;
  if(pl>pr) return 0;                  // 空子树高度为0
  for(k=il;k<=ir;k++)                  // 先序第一个是根，在中序里找根的位置
    if(in[k]==pre[pl]) break;
  h1=height(pl+1,pl+(k-il),il,k-1);    // 递归求左子树高度
  h2=height(pl+(k-il)+1,pr,k+1,ir);    // 递归求右子树高度
  return (h1>h2?h1:h2)+1;              // 高度=左右子树较高者+1
}
int main(){
  int n;
  while(std::scanf("%d",&n)==1){       // 一直读到文件结束
    std::scanf("%s%s",pre,in);
    std::printf("%d\n",height(0,n-1,0,n-1));
  }
  return 0;
}

复杂度分析

每次递归都要在中序序列里线性查找根结点的位置，每个结点都会被当作根处理一次，每层查找花费 O(N)，所以总时间是 O(N²)。空间上递归栈的深度等于树的高度，最坏情况下树退化成一条链，深度是 O(N)。N 不超过 50，运行非常快。