一、二叉树(60分)
给你一个整数序列，用这些数构成一个完全二叉排序树，输出此二叉树的层序遍历序列。
输入的第一行是一个整数n，表示这个整数序列的长度，输入的第二行包含n个整数，每个数代表完全二叉排序树的一个节点，现在需要输出由这n个整数构成的完全二叉排序树的层序遍历序列。
输入样例：
1856 987 -25 0 1021 -238 399 12 77 -1 72190 -25 -168 -41367 3218 12 0 -25
输出样例：
12 -1 987 -25 0 77 3218 -238 -25 0 12 56 399 1021 72190 -41367 -168 -25
样例解释：
输入样例对应的完全二叉排序树如下图所示
思路分析
二叉排序树有一个特点，它的中根序列是非递减的，因此如果对输入的序列进行非递减排序，那么就相当于得到了这棵树的中根遍历序列，然后再根据这棵树是完全二叉树，就可以得到此树的具体结构。当然，对于此题来说，我们完全没有必要真的将树的结构重构出来，我们只要能够想办法得到它的层序遍历序列即可。
假设现在有一棵节点数目为 n n n的完全二叉排序树，它的中序遍历序列的第一个元素在数组中的下标是 l I d x lIdx lIdx，那么我们可以做如下数学演算。
树的高度 h = ⌊ l o g 2 n ⌋ h=\lfloor log_2n \rfloor h=⌊log2n⌋，高度从0开始。除去最后一层，树的其余节点的数目 r e m a i n = 2 h − 1 remain=2^h-1 remain=2h−1。树的最后一层的节点数目 l a s t = n − r e m a i n last=n-remain last=n−remain。理论上，高度为h的完全二叉树的最后一层可以有的节点数目 l a s t M a x = 2 h lastMax=2^ h lastMax=2h。记左子树的节点数目为 l N u m lNum lNum。若 l a s t ≥ l a s t N u m / 2 last \ge lastNum/2 last≥lastNum/2，则说明左子树是满二叉树， l N u m = 2 h − 1 lNum=2^h-1 lNum=2h−1。若 l a s t < l a s t N u m / 2 last < lastNum/2 last<lastNum/2，则说明左子树的最后一层没有填满， l N u m = 2 h − 1 − 1 + l a s t lNum=2^{h-1}-1+last lNum=2h−1−1+last根节点在数组中的下标 r o o t I d x = l I d x + l N u m rootIdx=lIdx+lNum rootIdx=lIdx+lNum。左子树中序遍历序列的第一个元素在数组的下标是 l I d x lIdx lIdx，长度为 l N u m lNum lNum。右子树中序遍历序列的第一个元素在数组的下标是 r o o t I d x + 1 rootIdx+1 rootIdx+1，长度是 n − l N u m − 1 n-lNum-1 n−lNum−1。
通过上述的数学演算，可以根据中序遍历序列求出这棵完全二叉排序树的根节点，因为现在要求的是层序遍历序列，所以不能用递归的方法求左子树和右子树的根节点，而应该用队列来求。
源代码
#include <bits/stdc++.h>using namespace std;int arr[105];queue < pair<int, int> > q;//求在arr数组中，从lIdx开始，长度为n的序列所构成的完全二叉排序树的根节点void root(int lIdx, int n) {if (n <= 0)return;int h;//树的高度，从0开始int lNum; //左子树节点数目int remain;//除去最后一层，其余节点的数目int last; //最后一层的节点数目int lastMax; //理论上，最后一层可以有的最大节点数目int rootIdx; //根节点在数组中的下标h = log2(n);//在由float转为int的过程中，会自动实现向下取整remain = pow(2, h) - 1;last = n - remain;lastMax = pow(2, h);if (last >= lastMax / 2)lNum = pow(2, h) - 1;elselNum = pow(2, h - 1) - 1 + last;rootIdx = lIdx + lNum;cout << arr[rootIdx] << " ";q.push(make_pair(lIdx, lNum));q.push(make_pair(rootIdx + 1, n - lNum - 1));}int main(){int n;cin >> n;for (int i = 1; i <= n; i++) cin >> arr[i];sort(arr + 1, arr + n + 1);q.push(make_pair(1, n));while (!q.empty()) {auto top = q.front();q.pop();root(top.first, top.second);}return 0;}/*1856 987 -25 0 1021 -238 399 12 77 -1 72190 -25 -168 -41367 3218 12 0 -2512 -1 987 -25 0 77 3218 -238 -25 0 12 56 399 1021 72190 -41367 -168 -25*/
二、栈(40分）
给你一个函数调用过程，求调用的最大嵌套深度所对应的函数名，并输出调用路径，同时输出这个函数父函数（调用者）的个数和被调用的次数。同一个函数，如果有多条调用路径都可使其嵌套深度最深，则只输出第一条调用路径。
输入的数据中，若为1 funcName的形式，则表示调用funcName这个函数，若输入的是0，则表示结束对嵌套深度最大的函数的调用。
先看第一个测试用例。
1 main1 input01 area01 findA1 area001 findB1 get000
首先是对main函数的调用，调用之前栈中什么也没有，调用之后栈中只有main函数，如下图所示。
main函数调用input函数
input函数调用结束
main函数调用area函数
area函数调用结束
main函数调用findA函数
findA函数调用area函数
area函数调用结束
findA函数调用结束
main函数调用findB函数
findB函数调用get函数
get函数调用结束
findB函数调用结束
main函数调用结束
从上面的调用过程可以看出，最大嵌套深度是3，对应的函数有两个，分别是area和get。area的调用路径是main-findA，总共有两个函数调用过area，这两个函数分别是input和findA，area总共被调用过两次。get的调用路径是main-findB，总共有一个函数调用过get，这个函数是findB。所以上面的测试用例输出结果应该是：
area main-findA 2 2get main-findB 1 1
下面再来看一个更复杂一点的测试用例。
1 main1 input01 mysqrt01 findA01 findB1 area1 mysin01 mycos01 mysqrt0001 findC1 area1 mysin001 mysqrt1 max0001 output00
对于这组输入数据，仍然可以用前面画栈结构图的方法来表示调用过程，限于篇幅，我这里就不再画了。大家应该注意到，对于这组数据，函数的调用次数和调用者的个数已经不再相同，这是因为一个函数可能多次调用另一个函数，比如area函数调用了两次mysin函数，那么mysin函数的调用者的个数是1，因为只有area函数对其进行过调用，但是调用次数却是2，因为它被调用了两次。同时还要注意，mysin函数有两条最深调用路径，分别是main-findB-area-mysin和main-findC-area-mysin，按照之前说过的输出规则，对于同一个函数，如果有多条最深调用路径，只输出第一条，所以最终的输出结果如下。
mysin main-findB-area 1 2mycos main-findB-area 1 1mysqrt main-findB-area 3 3max main-findC-mysqrt 1 1
思路分析
这道题虽然看起来像是考察栈，但是却不能直接用C++STL中的stack，因为需要记录栈中的内容，用stack操作起来会非常麻烦，所以最终我选择用vector<string>来模拟栈，变量depth相当于栈顶指针，当发生函数调用时，先将被调函数入栈，再令depth自加，当调用结束时，直接令depth自减。
因为本题是一道模拟题，不涉及复杂的算法，所以不再进行过多的阐述，我已经在代码中加了详细的注释，读者可以边阅读代码，边体会解题过程。
源代码
#include<bits/stdc++.h>#include<unordered_map>#include<unordered_set>using namespace std;vector<string> callStack;//相当于栈，存放函数名unordered_map<string, int> numOfCalls;//调用次数unordered_map<string, unordered_set<string> > numOfCaller;//统计有多少个父函数，用unordered_set的目的是去重vector<vector<string> > ans;//存放最终结果int main() {callStack.resize(205);int type;string funcName;int depth = 0, maxdep = 0;//分别是当前的调用深度和目前为止最大的调用深度while (cin >> type) {if (type == 1) {//函数调用cin >> funcName;numOfCalls[funcName]++;//记录函数被调用的次数if (depth != 0) {//深度不为0，说明当前被调用的函数一定有调用者（如果当前被调用的函数是main，则无调用者）string caller = callStack[depth - 1];numOfCaller[funcName].insert(caller);//将funcName函数的所有调用者都保存起来}callStack[depth++] = funcName;//先将funcName入栈，再令调用深度加1if (depth > maxdep) {//更新最大深度ans.clear();ans.push_back(callStack);maxdep = depth;}else if (depth == maxdep) {//最大深度相同int flag = false;//判断是否有同一个函数，存在多条最深路径的情况for (auto v : ans) {if (v[maxdep - 1] == funcName) {flag = true;break;}}if(flag == false)ans.push_back(callStack);}}else {//调用结束depth--;}}for (int j = 0; j < ans.size(); j++) {funcName = ans[j][maxdep - 1];//嵌套深度最大的函数cout << funcName << " " << ans[j][0];for (int i = 1; i < maxdep - 1; i++)//输出调用路径cout << "-" << ans[j][i];cout << " " << numOfCaller[funcName].size() << " " << numOfCalls[funcName] << endl;}return 0;}
