從LeetCode學演算法 - 98 Tree (13) / DFS (10)

0129. Sum Root to Leaf Numbers (Medium)

寫在前面

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

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

Question

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
9
Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

分析/解題

給定一個二元樹，當中只有數字0~9，
每個根到葉子的路徑可以表達一個數。
舉例來說，1->2->3可以表達123。
找出所有的根到葉的數字的總和。
(葉的定義是沒有子節點的節點)

這題雖然標註為Medium，但其實並不那麼難思考，
只是定義要弄清楚而已。

首先，假設我們在某個節點n，它如果左節點和右節點都沒有的話，
意味著它是葉(leaf)，這時數字就要計入總和；
如果有其中一個成立的話，我們應該要往下走，
並記錄之前經過的節點値，這樣子在遇到葉的時候才能夠結算。

那麼自然，由於每棵樹只有0~9，
所以從一層樹到下一層的時候，原先經過的數字的作用會放大10倍。
也就是說，從上一層下來的時候，如果所在是葉的話，
我們應該要把這個數字乘以10以後，加上現在的節點値 。

因此，我們只要遍歷完整棵樹，將葉子加總 起來即可。
寫成流程應該如下：

檢查根節點是否為NIL，如果是，直接回傳0(此路不通)
計算上面下來的值(last)到當前根節點的值(now)的結果，
now = last * 10 + root.val
如果左右節點均為NIL，直接回傳now 即可(當前節點為葉)
將root.left, now及root.right, now 分別傳入做遞迴計算左右子樹的和 ，
最後加總起來並回傳 。
所以我們會先沿著最左邊一路到最底，然後依序將所有節點走過，
這樣子是先往深處走，所以是所謂的深度優先搜尋(DFS)的方法。

另外一方面，留意由於我們最開始已經檢查了root是否為NIL，
所以在傳入左右子節點時，可以讓前面這條檢查來確認NIL的狀況，
也就不用再先檢查節點是否為空了。

依此，寫成程式碼如下：

Java

Java可以使用相同的函式名稱，傳入不同長度的參數 來處理。

Python

Python的部分，我們直接設定預設值 ，這樣就可以通用了XD
當從根節點開始時，由於只傳入root, 自然last會是0。

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

「時間/空間複雜度？」
(O(N)/O(1), 如果算上call stack的部分的話，
平均空間複雜度是O(logN) (DFS的深度))

相似及延伸

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

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

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