在線編程介紹
阿里雲開發者社區在線編程產品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費在線刷題神器。題庫來自筆試模擬題、算法大賽模擬題等，界面整潔明瞭，操作簡單，為用戶營造專心答題的學習環境。點擊鏈接開始體驗：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)
看完之後是不是有了想法了呢，快來練練手吧>>查看題目：蘋果收穫程序
