题目描述给定一棵二叉树每个节点有一个整数值正数表示该节点掉落的叶子数量。节点在水平方向上排列左子节点在父节点左侧111单位右子节点在父节点右侧111单位。所有叶子垂直下落最终在地面上形成若干堆每堆对应一个水平位置。要求计算每个水平位置上的叶子总数并从左到右输出。输入以前序遍历方式描述树空子树用−1-1−1表示。输入以单独一个−1-1−1结束。输入格式多组数据每组数据为前序遍历序列整数以−1-1−1结束。最后一个测试用例为单独一个−1-1−1。输出格式对于每组数据输出Case X:然后输出一行从左到右列出每个水平位置的叶子总数用空格分隔。每组输出后跟一个空行。样例输入5 7 -1 6 -1 -1 3 -1 -1 8 2 9 -1 -1 6 5 -1 -1 12 -1 -1 3 7 -1 -1 -1 -1 -1输出Case 1: 7 11 3 Case 2: 9 7 21 15题目分析本题通过前序遍历构建树并在递归过程中记录每个节点的水平位置。根节点位置为000左子树位置减111右子树位置加111。使用mapint, int累加每个位置的叶子总数map自动按键水平位置升序排列因此输出时直接遍历即可。解题思路全局mapint, int piles键为水平位置值为叶子总数。递归函数parse(leaves, position)若leaves -1返回。否则piles[position] leaves。读入左子树的根值递归调用parse(left, position - 1)。读入右子树的根值递归调用parse(right, position 1)。主循环读入根值若为−1-1−1则结束否则调用parse然后输出结果。复杂度分析每个节点访问一次时间复杂度O(N)O(N)O(N)其中NNN为节点数。空间复杂度O(N)O(N)O(N)。代码实现// The Falling Leaves// UVa ID: 699// Verdict: Accepted// Submission Date: 2016-08-27// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;mapint,intpiles;voidparse(intleaves,intposition){if(leaves!-1)piles[position]leaves;cinleaves;if(leaves!-1)parse(leaves,position-1);cinleaves;if(leaves!-1)parse(leaves,position1);}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intleaves,cases0;while(cinleaves,leaves!-1){piles.clear();parse(leaves,0);coutCase cases:\n;intlength0;for(autopile:piles){if(length0)cout ;coutpile.second;}cout\n\n;}return0;}总结本题通过递归前序遍历构建树并同时计算水平位置累加值利用map自动排序简化输出。关键点包括正确理解前序遍历与树结构的关系。使用map存储水平位置到叶子总数的映射。注意递归中左右子树的读取顺序。该解法简洁高效适合作为树的遍历和映射应用的练习。