0257. Binary Tree Paths (Easy)
Question
Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
| |
| |
| |
| |
分析/解題
給定一個二元樹，回傳其所有根到葉的路徑。
這題是Easy難度的題目，剛好藉由它來講一下回溯法(Backtracking) 。
這個題目看起來挺簡單的，如果沒有特別要求的話，寫起來也不難，
依照遞回的模式就可以順利解決，
思路大致上是每走一步就將root的值串上path字串 ，
直到左右均無節點，表示已走到葉節點了，即可將其放到結果res中。
所以一般可能會寫成這樣：
可以通過但不盡理想的遞回解
這麼做其實不盡理想，
因為我們會發現裡面的每一個tmp其實都是使用一個新的變數 ，
顯然這件事情會讓我們花費更多的空間(因為產生新的變數)。
怎麼辦呢？這時候就到了回溯法上場的時候了。
我們之前有介紹過DFS/BFS ，
分別代表著深度優先搜尋 和廣度優先搜尋 ，
如這題前面的解法其實也可以當作DFS來看待，
而回溯法的概念又更廣泛一些 ：
在每個階段將所有可能性列出 ，
經過檢查排除 掉不可能的解後，往下一個階段 進行搜尋；
如果這個階段的所有分支均不成立 ，
則回復到上一個階段 的搜尋，並取消 掉這個階段所造成的影響。
(過程中視要求，可在找到所有答案後才回傳，或者找到第一個答案就回傳)
簡單來說，就是一個一個試，
走錯了就回頭，而且記得先前** 試的痕跡要處理掉**就對了XD
聽起來可能還是有點抽象，我們講這題的實作方式好了。
要進行回溯法，首先要確立要處理的對象 。
例如這題裡面最重要的是節點經過的路徑 ，
那麼我們應該可以將當前的路徑當作主要處理的對象：
每次在遞迴函式中應該要做的事情有：
- 將當前的根節點 加到路徑 的ArrayList中
- 如果左節點 存在，遞迴進行左子樹 的部分
- 如果右節點 存在，遞迴進行右子樹 的部分
- 如果左右節點均不存在 ，表示該路徑是答案要求的其中一條 ，
將整個路徑內的節點值按照要求的格式輸出到結果res中 - 走完前4步，這個階段的可能性均搜索完畢 ，
所以要回到上一個階段，這時在1.的時候加入的根節點應該要被移除 ，
因為上一個階段並沒有它。
可以看到在回溯法中，路徑的部分是所有函式共用 的，
所以只要妥善處理用完後復原，即可使用一個List來處理整個樹的狀況，
這個List最大的占用空間就是這棵樹的深度 。
依此，我們可以寫出其程式碼。
Java的部分，這邊用DFS來命名遞迴的函式名，
也可以叫getPath，可依讀者喜號命名。
使用StringBuilder來進行字串的整理(加上”->”)，
以及使用ArrayList/LinkedList來處理path相關的部分。
(應該是用哪個都可以啦XD 題目只限定List)
最後不要忘記每次該階段做完要將最後一個進行移除(remove)。
Java
Python的部份我們可以直接使用List來處理，
並且利用join 的特性可以很方便地串接所有的path。
最後一樣不要忘記移除當階段的痕跡(pop )。
Python
面試實際可能會遇到的問題
「時間/空間複雜度？」
(時間複雜度為O(N)(因為要掃過整棵樹)；
空間複雜度的部分，使用的path在平衡的狀態下複雜度是O(logN)
而最後的res部分如果用個數來看的話，完美的二元樹深度是O(logN)，
路徑數是O(N)，所以總占用空間是O(N * logN) )
相似及延伸
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~