Microsoft coding(已知先序和中序序列，求树).
Microsoft | Coding
from CareerCup by sarthak
Given a preorder and inorder traversal of a binary tree, can you reproduce the tree? if yes, then write a function using C/C++ that builds the tree and returns the root node of the tree.
#include < stdio.h>#include <iostream>#include <stack>#include <Windows.h>#include <string>using namespace std;#define CHECK(x) {if(!(x)){printf("Fatal error: " #x);exit(0);}}void Trace(char* szFormat,
)
{
va_list l; char s[500]; va_start(l,szFormat); vsprintf(s,szFormat,l); OutputDebugStringA(s);
}typedef class BiTNode{public: char data; BiTNode *lc,*rc; }*BiTree;//根据先序和中序创建二叉树/************************************************************************//* Microsoft | Codingfrom CareerCup by sarthakGiven a preorder and inorder traversal of a binary tree, can you reproduce the tree? if yes, then write a function using C/C++ that builds the tree and returns the root node of the tree. *//************************************************************************/BiTree BiTreeCreate(string preStr,string inStr){ CHECK(preStr.size() ==inStr.size() && inStr.size()>0); char c=preStr[0]; int pos=inStr.find_first_of(c); CHECK(pos!=-1); BiTree p=new BiTNode; p->data=c; if(pos==0) p->lc=0; else
{
string ins1=inStr.substr(0,pos); string pres1=preStr.substr(1,pos); Trace("ins1:%s ,pres1:%s",ins1.c_str(),pres1.c_str()); p->lc=BiTreeCreate(pres1,ins1);
} if(pos==preStr.size()-1) p->rc=0; else { string ins2=inStr.substr(pos+1); string pres2=preStr.substr(1+pos); Trace("ins2:%s ,pres2:%s",ins2.c_str(),pres2.c_str()); p->rc=BiTreeCreate(pres2,ins2); } return p;}void TraverseInOrder2(BiTree T){ if(T) { TraverseInOrder2(T->lc); cout<<T->data; TraverseInOrder2(T->rc); }}//先序遍历void Traverse1Order(BiTree T){ if(T) { cout<<T->data; Traverse1Order(T->lc); Traverse1Order(T->rc); }}void Test(){ BiTree tree=BiTreeCreate("ABDECFG","DBEAFCG"); cout<<"preOrder:"<<endl; Traverse1Order(tree); cout<<endl<<"inOrder:"<<endl; TraverseInOrder2(tree); cout<<endl;}