1161. Maximum Level Sum of a Binary Tree (Medium)

Question

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is ** maximal**.

Example 1

1
2
3
4
5
6
7

Input: [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Note:

1. The number of nodes in the given tree is between 1 and 10^4.
2. -10^5 <= node.val <= 10^5

分析/解題

給定一個二元樹的根節點，若將該層(level)稱為1，
其子節點所在層稱為2，……以此類推，
嘗試找出最小的x層，這層的所有節點和是在所有層裡面最大的 。

這題其實存在不同的解法，若讀者有興趣的話也可以使用DFS的解法，
本篇只介紹BFS的作法。

如果有看過先前對於Tree的介紹的話，
我們應該有提到過不同方式的走訪，而這題問的，
如果限定在迭代法解的話，就適合使用層序走訪(level-order traversal) 。
層序走訪的概念很簡單：
每次先走完這一層的所有節點，再走下一層的所有節點 。

用遞迴來看的話顯然是沒辦法的，
因為每次往下都是走往下一層 (左子樹或右子樹)，
所以我們需要用非遞迴的方式，並使用Queue來作輔助。

大概步驟會像這樣子：(下面將Queue命名為q)

1. 將根節點放入q中

2. 當q中有節點時，先求q現在的節點數量cnt
   (註：這個節點數量就是目前這整層的所有節點數 )

3. 開始一個迴圈，這個迴圈執行cnt次 :
   3-a. 每次從q中取出一個節點n ，並將其值加到當前總和total 中
   3-b. 檢查左右節點，如果不是NIL則放進q中
   (註：第3步做完以後，
   q中前一層的cnt個節點應該已經全數移除，並加入下一層的所有節點)

4. 檢查total是否大於當前的最大總和 ，
   若是，則替換掉最大總和 及所求答案的層數

5. 遞增當前的層數(level)

6. 重複2~5的動作，直到q中沒有任何節點為止

由上面的步驟可知，每一次我們均藉由Queue來走遍所有同一層 的節點。
在非樹的題目中，類似的作法是先走所有離自己一步距離的可能，
再往下一層去處理，由於是先求廣度 ，
這樣子的作法我們稱之為廣度優先搜尋(BFS, Breadth-First Search) 。

Java的部分，我們可以使用不同的Queue的實作方式，
讀者可以選用ArrayList, LinkedList或ArrayDeque。
(一般來說ArrayList效率會較差，
有人說ArrayDeque號稱比LinkedList好，
但筆者實測看起來沒有明顯差異XD)

Java的Queue放入和取出的寫法是offer/poll ，總數使用size ，
檢查是否為空則用isEmpty 。

Java

Python的部分則使用前面提過的deque 來處理，
放入和取出分別是append 跟popleft ，總數使用len ，
是否為空則直接拿其本體來判斷 (裡面是空的則會是False )

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(N)，因為會遍歷整棵樹，而空間占用最大的時候會占用最下面的一整層，所以最糟的狀況也會是O(N)。)

「題目有告訴我們node總數最大是10^4，如果這棵二元樹是處在平衡的狀態的話，有沒有比較方便的解法？」
(平衡二元樹代表中間該填滿的都填滿了，
所以可以利用這點去算最大的層數，
新增一個陣列/串列來記錄某一層的總和；
直接利用層數來進行DFS，將走到的點的值加到對應的位置，
最後加總完以後再來看哪一個level總和最大。)

「可以用DFS來解這題看看嗎？」
(可以，只是traversal的時候記得要傳遞層數的值，
並且開一個ArrayList/List來存放每層的總和。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~