0687. Longest Univalue Path (Easy)
Question
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
The length of the path between two nodes is represented by the number of edges between them.
Example 1
Input:
| |
Output: 2
Example 2
Input:
| |
Output: 2
Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.
分析/解題
給定一個二元樹，尋找其最長的路徑長，
當中的所有節點必須擁有相同的值。
這條路徑通過或沒有通過根節點均可。
(路徑長度的定義為兩個節點之間經過的邊(edge)的數量)
由於很早我們就介紹過樹的基本性質了，
(印象模糊的讀者請回頭參照0100. Same Tree)，
在此就不再贅述。這題嘗試要找相同值的路徑，
但又不限定要通過root，該怎麼思考呢？
我們可以先考慮怎樣可以算一條相同值的路徑 。
一條相同值的路徑有可能有以下兩種狀況：
- 從一個頂點下來，
每次選擇往左節點走或往右節點走，到一個位置停下。
例如：
| |
當中的5-5-5就是一條相同值的路徑。
- 從一個頂點進行分岔，左右各自走到一個位置停下。
例如：
| |
當中的粗斜體的4-4-4 就是一條從頂點往左右分岔所得到的路徑，
可以選擇從左下的4 -> 中間的4 -> 再到右邊的4 ，這樣連成一個路徑。
但從這邊來看可以發現，這條路徑就無法把root的4算在內，
因為不管怎麼連，我們都沒辦法一筆不重複將這4個4走完。
因此，我們可以得知：
對於某個節點來說，有經過它所能得到的最長路徑，
有可能是從它的上面連下來(分岔點在它的上面 )，
也可能是以它自己為分岔點 ，左右各自找完和它值相同的節點路徑。
在第一個情況來說，要求它的上一個節點值和它的值相同；
第二個情況來說，則要將左右和它的值相同的路徑長相加 。
所以我們可以定義一個count函式，
回傳以某個節點值來說，其下的最長所能得到的相同值的路徑長，
當中計算的時候一邊留意當下最長的路徑長並進行更新。
我們將整個題目的答案(相同值的最長路徑長)叫做mx(叫result也可以)，
流程順序應為：
- 一開始應該先檢查root是否為NIL ，
如是，回傳0 (因為沒有路徑)，否則呼叫count函式，
檢查它所能得到的相同值的最長路徑長 。
(傳入root節點，及當下的路徑節點值root.val ) - 在count當中，
同樣應先檢查傳入的節點值是否為null，
接下來為了要知道左右路徑的相同值的最長路徑長，
應該要分別帶入其left/right節點及當前節點的值 進去檢查，
假設得到的結果分別為l/r 。 - 依照2的定義，l + r的值代表了一條可能的相同值路徑，
所以要拿它和mx比較，將較長的路徑值更新。 - 如果當前的節點值 和**傳進來的路徑節點值兩者相同，
代表有機會可以考慮上面提到過的
「從一個頂點下來，每次選擇往左節點走或往右節點走，
到一個位置停下。」的狀況，
這時候要回傳的值會是左右路徑長較長的部分+1。
(因為要包含左節點/右節點到當前節點的這個路徑) - 上面的判斷不成立的話，代表路徑從上面下來到這邊斷掉了。
(值不相同)，這時候應該回傳0，代表相同值路徑到這邊沒辦法繼續。**
上面的流程順序，請讀者務必自行畫圖推導，
會比較清楚整個思考過程。
依此，寫成程式碼如下：
Java
Java的部分mx直接宣告一個class變數即可，其它就是使用Math.max，
及檢查null的部分，並不複雜。
Python
Python的話，可以使用self.mx來宣告，
並且在__init__時進行處理，
其它就是一樣注意呼叫時不要忘記用self 即可。
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(N)/O(1)，如果空間要算上call stack的部分的話，
則是O(TreeNode的高度)。)
相似及延伸
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~
感謝大家對這系列文章的支持！這邊跟大家自我工商一下：
筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**