7-1 还原二叉树 (25 分)

题目:

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

代码:

#include <bits/stdc++.h>
using namespace std;
struct btnode {
 char  value;
  btnode *lc;
  btnode *rc;
};
char pre[55];
char pos[55];
int n;
int ans=0;
btnode* buildtree(char pre[],char pos[],int n,int cnt)
{
  if(n==0) return NULL;

  btnode *F=new btnode;
  int root=pre[0];
  F->value=root;

  int k=0;
  for(int i=0;i<n;i++)
  {
    if(pos[i]==root)
    {
      k=i;
      break;
    }
  }
  cnt++;
  F->lc=buildtree(pre+1,pos,k,cnt);
  if(F->lc){
      ans=max(cnt,ans);
  }
  F->rc=buildtree(pre+k+1,pos+k+1,n-k-1,cnt);
    if(F->rc){
      ans=max(cnt,ans);
  }
 
  return F;
}

int main()
{
  cin>>n;
  cin>>pre;
  cin>>pos;
   // cout<<ans;

  btnode *F=buildtree(pre,pos,n,1);
   if(n==1) ans=1;
  cout<<ans;
  return 0;
}

上一篇:系统自动更新方案(2)上传:上传本地目录到服务器的过程


下一篇:网课杂记其四