從LeetCode學演算法 - 42 Backtracking (1) / Tree (8)

0257. Binary Tree Paths (Easy)

寫在前面：
如果覺得這篇有幫助到您的話，
請幫我隨手點開最下面的SHOW EMBED並拍5下手~
(當然，Medium的拍手也可以多拍幾下啦XD)
這樣我再寫個十多篇以後應該就有買一杯咖啡的$$了XDDDDD
(聽起來超少哈哈)

Question:
Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:
   1
 /   \
2     3
 \
  5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3

分析/解題：
給定一個二元樹，回傳其所有根到葉的路徑。
這題是Easy難度的題目，剛好藉由它來講一下回溯法(Backtracking)。
這個題目看起來挺簡單的，如果沒有特別要求的話，寫起來也不難，
依照遞回的模式就可以順利解決，
思路大致上是每走一步就將root的值串上path字串，
直到左右均無節點，表示已走到葉節點了，即可將其放到結果res中。

所以一般可能會寫成這樣：

可以通過但不盡理想的遞回解

這麼做其實不盡理想，
因為我們會發現裡面的每一個tmp其實都是使用一個新的變數，
顯然這件事情會讓我們花費更多的空間(因為產生新的變數)。
怎麼辦呢？這時候就到了回溯法上場的時候了。