← 返回目录

算法笔试模拟题精解之“苹果收获程序”

第 43 / 74 卷日期：

算法笔试模拟题精解之“苹果收获程序”

贡献者 | 郭达彬

简介：因为每次下落时，苹果树每一层的节点都会往下掉一层。由此可以想到，

如果苹果树某一层的节点的数目为奇数时，这一层的节点的苹果掉落到第一层时，由

于一个节点只能存储一个二进制位的原因，只会剩下一个苹果。而如果苹果树某一层

的节点数目为偶数，这一层的节点的苹果掉落到第一层时，剩下的苹果数目为 0。

题目描述

题目等级：容易

知识点：深度优先搜索 /DFS

查看题目：苹果收获程序

Alice 和 Bob 在春天的时候种下了一棵苹果树，为了吃到苹果，他们每天都会

去给苹果树浇水。一眨眼到了苹果成熟的时候，但是他们却因为平时照顾苹果树太累

了，没有更多的精力去收获苹果。身为程序猿的 Bob 灵机一动，写了一个自动收获

苹果的程序。

这个程序把苹果树简化成了一个拥有 n 个节点，根节点为 1 的树，每个节点有 1

个苹果，苹果会在程序的作用下同时往根节点的方向掉落。

但是这个程序有一个致命的 Bug：每当有两个苹果同时掉落到同一个节点的时

候，这两个苹果会在 Bug 的作用下消失。

每当 1 苹果落到根节点 1 的时候，Bob 就可以收获 1 个苹果。

Bob 想要预测他们最后可以通过程序收获多少个苹果。

输入内容有两行。

第一行有一个正整数 n(2<=n<=10^5)，表示树有 n 个节点。

第二行有 n-1 个数 p2,p3,...,pn，(1<=pi 滚落到节点 2 上面的苹果会因为 bug

而消失的只剩一个。）

输出一个数字，表示 Bob 最后能收获的苹果数量。

示例 1

输入：

5

[1,2,2,2]

输出：

3

注意

  1. 苹果的掉落速度是相等的，即每次都会掉落到与当前节点直接相连的节点上。
  2. 只要有苹果出现在根节点 1 上面就会被收获。

解题思路

苹果收获程序在正常情况下，有多个苹果落到同一节点时，应该会是一个相加的

情况。结合这个 BUG 的情况，可以猜想，这个程序的 BUG 也许是因为这棵树每个

节点只能存储一个二进制位导致的，在这种情况下出现的 BUG 和题目中的相符。

因为每次下落时，苹果树每一层的节点都会往下掉一层。由此可以想到，如果苹

果树某一层的节点的数目为奇数时，这一层的节点的苹果掉落到第一层时，由于一个

数目为偶数，这一层的节点的苹果掉落到第一层时，剩下的苹果数目为 0。

因此可以统计每一层有多少个节点来解决这个问题，根节点 1 是第一层，掉落到

一层的节点是第二层，以此类推，通过判断一个节点会掉落到的层数来判断该结点当

前是第几层。遍历数组，用一个数组 count 记录每一层拥有的节点数，遍历数组，计

算出一个节点所在的层之后，在 count 数组中将该层拥有的节点数加一。最后判断哪

些层的节点数为奇数，这些层每层可以收获一个苹果，累加后即可得到答案。

提交以后，发现还有一些测试用例无法通过，通过分析以后发现，还需要注意一

个问题。在遍历数组计算每个节点所在的层时，需要注意，如果数组中的数字表示这

个节点会掉落到自身节点的位置上，也就是这个节点的苹果不会往下层掉，会永远留

在这个节点，因此在统计每层的节点数时，这个节点不该被统计，而掉落到这个节点

的其他节点的苹果也永远不会掉落到第一层，因此这些节点也不能被统计，不属于任

何层，不被统计进 count 数组。

时间复杂度：O(n)

空间复杂度：O(n)

看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：苹果收获程序

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”