在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的 第67题：苹果收获程序 的题目解析，具体如下：

题目描述

题目等级：容易
知识点：深度优先搜索/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)

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