1530. Number of Good Leaf Nodes Pairs (Medium)

寫在前面

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/advleetcode

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/allleetcode

Question

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of ** the shortest path** between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1

1
2
3

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2

1
2
3

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3

1
2
3

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Example 4

1
2

Input: root = [100], distance = 1
Output: 0

Example 5

1
2

Input: root = [1,1,1], distance = 2
Output: 1

Constraints

• The number of nodes in the tree is in the range [1, 2^10].
• Each node’s value is between [1, 100].
• 1 <= distance <= 10

分析/解題

這題是2020/07/26舉辦的199th LeetCode Weekly Contest的第3題。
給定一個二元樹的根節點root和一個整數距離distance，
如果兩個不同的葉節點配對，其最小距離小於等於distance，
我們就將其稱之為好(good)。
試回傳這棵樹好的葉節點配對的總數。

我們先前應該已經提到過葉節點就是指左右都沒有連接節點的節點 ，
那麼，這題要怎麼思考呢？

我們不妨先留意一下題目給定的條件：
節點數量是1~2¹⁰，由於2¹⁰=1024 ，所以最壞的狀況，
遞迴的數量也就1024而已，所以應該可以不會超過call stack的上限。
接著，1≤distance≤10決定了我們在遞迴時，
可以適度修剪我們要處理的節點。

那這題該怎麼思考呢？
由於我們在求的是最短距離，假定我們要看兩個節點x, y，
那麼最短路徑肯定是從x往上走到x, y的最低共同祖先，
再往下走到y的位置。

如果我們知道x, y的LCA(最低共同祖先)n，
又知道n的左子樹的所有葉節點各自的深度，
及右子樹的所有葉節點各自的深度，
那麼我們就可以知道以n為LCA時，正確的節點對有哪些。
怎麼知道？就迴圈加起來就好了嘛！

那我們又怎麼知道某個節點n的左右子樹的葉節點深度呢？
我們可以先用dfs往深處走，走到出現葉節點的時候，
將其記錄為距離1並往上傳(因為這時候左右也都沒得走了)；

那在某個非葉節點的n 時，我們應該可以從dfs的結果，
分別獲得左右子樹的各個葉節點離n的距離 。
我們將兩個距離的列表分別叫作llt跟rlt (left list, right list)，
從llt跟rlt分別成對取出來相加，
每發現一組葉節點距離相加小於等於10，全局的解就加1 。

做完檢查以後該做什麼呢？
裡面所有的葉節點應該可以往上通用，對吧？
可是我們左子樹和右子樹往上都導到當前的節點再往上，
再往上的深度應該都要加1 才對！
所以我們應該將llt和rlt裡面的所有值都分別+1以後，
放入一個新的list，這裡命名為merge，再將其往上傳。

因此，整個流程會大致如下：

1. 定一個class變數cnt，用來記錄成功配對的葉節點對的總數
2. 在主函式裡，先檢查root是否為NIL，是的話直接回傳0
3. 將root和distance帶入遞迴函式dfs中
4. 回傳cnt

而在dfs函式中，我們要做的事情是：

1. 若n為NIL，回傳空的串列
2. 若n的左右節點均為NIL ，則回傳一個裡面只含一個1的串列
3. 呼叫dfs(n.left, distance) 及dfs(n.right, distance) 進行遞迴，
   取得回傳的llt 跟rlt (記錄兩邊葉節點深度的串列)
4. 初始化一個空的串列merge
5. 雙重迴圈，每當遇到llt和rlt的値**，
   兩兩相加會小於等於distance的狀況，就將 cnt遞增1**
6. 分別將llt和rlt的値全數+1後，加到merge 裡
   (這邊可以檢查值必須小於distance ，超過的話因為總路徑肯定超過， 所以不符的不用放到merge內)
7. 回傳merge

依此，寫成程式碼如下：

Java

由於需要一個一個取出，並且重複使用，
所以我們使用ArrayList 並使用get 來取得當中的值。
在雙重迴圈的時候，我們可以順便將外層的値處理一下放到merge內 ，
這樣後面就不用再重複一個新的迴圈處理。
(但內層的不能這麼做，因為會被重複執行)

Python

Python的部分，cnt的累計可以使用list comprehension，
處理符合的配對再來取len() ，這樣寫起來會比雙重迴圈方便許多。
llt和rlt則可以用類似的方式，最後將串列用加號組起來回傳。

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

「時間/空間複雜度？」
(O((log N)³)/O(log N)，因為只有葉節點需要被記錄，
空間應該跟最底層的節點數有關，而除了雙重迴圈外，
dfs的深度也跟這棵樹的深度有關，但這個部分會受到distance的制約，
所以實際應該比這個複雜度快不少)

相似及延伸

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

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

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve