学步园

根据网传的2014华为校园招聘的机试题目，而编写的代码。

/*
输入一个二叉树 格式为“单个字符+节点所在层次” 
比如根节点所在层次是1，它的两个子树都是2. 节点排列从左到右，然后再输入其中的某个（些）节点，
求得其深度。
第三题还有条件：层次不超过9层
输入：a1b2c2d3e3f3    ab
输出：3 2

[输入、输出有点随意]
*/

#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace  std;

static int maxLevel = 1;
struct Node
{
char ch;
int level;
Node* pLeft;
Node* pRight;

Node(char c, int level)
{
ch = c;
this->level = level;
pLeft = NULL;
pRight = NULL;
}
};

//每次添加新节点时， 将当前的树 按层次遍历添加到队列中
void InitialQueue(queue<Node*>& que, Node* pFirst)
{
que.push(pFirst);
queue<Node*> tempQue;
tempQue.push(pFirst);   //申请一个临时用于 操作的队列
while(pFirst)
{
if (pFirst->pLeft !=NULL)
{
que.push(pFirst->pLeft);
tempQue.push(pFirst->pLeft);
}
if (pFirst->pRight != NULL)
{
que.push(pFirst->pRight);
tempQue.push(pFirst->pRight);
}
tempQue.pop();

if (tempQue.empty())
{
break;
}
pFirst =  tempQue.front();
}
return;
};

Node* CreateTree(char* source)
{
Node  *pRoot = new Node(source[0], source[1]-48);
char* pCopy = source+2;

while (*pCopy != '\0')
{
queue<Node*>  que;
InitialQueue(que, pRoot);   //层次遍历整个二叉树
char ch = *pCopy;
int level = *(++pCopy)-48;
Node*  pNewNode = new Node(ch, level);

while (!que.empty())    //队列不为空
{
Node* queNode = que.front();
if(queNode->level == pNewNode->level -1)     //此节点为 待插入节点的上层节点
{
if (queNode->pLeft ==NULL)
{
queNode->pLeft = pNewNode;
que.push(pNewNode);
break;

}else if (queNode->pRight == NULL)
{
queNode->pRight = pNewNode;
que.push(pNewNode);
break;

}else //此上层节点左右孩子已满，弹出
{
que.pop(); 
}
}else //若不为上层节点，弹出
{
que.pop();         
}
}
pCopy++;
}
return pRoot;
}

//获得输入节点在树中的位置

Node* GetPointer(Node* pRoot, char test)
{
queue<Node*> que;
que.push(pRoot);

while (pRoot)
{
if (pRoot->ch == test)
{
return pRoot;
}
if(pRoot->pLeft)
{
if (pRoot->ch == test)
{
return pRoot->pLeft;

}else
{
que.push(pRoot->pLeft);
}
}
if (pRoot->pRight)
{
if (pRoot->pRight->ch == test)
{
return pRoot->pRight;

}else
{
que.push(pRoot->pRight);
}
}
que.pop();      //注意对 队列为空的判断！
if (que.empty())
{
break;
}
pRoot = que.front();
}
return NULL;
}

//找到以输入节点为根节点的树的最大层数
int Ergodic(Node* pNode)
{

if (pNode == NULL)
{
return -1;
}

if (pNode->pLeft != NULL)
{
Ergodic(pNode->pLeft);
maxLevel = max(maxLevel, pNode->pLeft->level);
}

if (pNode->pRight != NULL)
{
Ergodic(pNode->pRight);
maxLevel = max(maxLevel, pNode->pRight->level);
}

return max(maxLevel, pNode->level);
}

vector<int> GetLevel(char* input, char* test)
{
//@1 构建树
vector<int> vec;
Node *pRoot = CreateTree(input);

//@2 找到输入节点在树中的位置
while (*test  !='\0')
{
char ch = *test;
Node* pPointer = GetPointer(pRoot, ch);
int tempLevel = pPointer->level;     //输入节点（根）所在的层数
maxLevel = tempLevel;
int maxLevel = Ergodic(pPointer); //找到以输入节点为根节点树的，叶子节点所在的最大层数
int level = maxLevel - tempLevel +1;
vec.push_back(level);
test++;
}

return vec;
}

int main()
{

char* input = "a1b2c2d3e4f3g4o4y5h5j6l7";
char* test = "abdeyjfcgohl";
vector<int> vec  = GetLevel(input, test);
cout<<input<<endl<<test<<endl;

for (unsigned int i = 0; i<vec.size(); i++)
{
cout<<vec[i]<<"   ";
}

return 1;
}