0404. Sum of Left Leaves (Easy)
寫在前面
容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/advleetcode
「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/allleetcode
Question
Find the sum of all left leaves in a given binary tree.
Example:
| |
| |
分析/解題
給定一個二元樹，試求所有左葉子的總和。
我們很久以前有提過二元樹的定義，
忘記的話，請再複習一下XD
而葉子的定義，就是它左右都沒有連接節點(NIL)！
這時候，你可能會說：
我知道，那我只要一直往左邊看就好啦！
呃……同學，你忘記了你的右子樹也可能產生左葉子 嗎XD？
範例中的15，不就是先從3的右節點20，
再往左節點來到15所得到的嗎？
那怎麼辦呢？
所以我們在檢查所在節點是不是葉子的時候，
還需要看看這個節點是不是從它的根節點往左邊走下來 的。
因此，我們可以每次分支往左右走，給出一個參數from，
分別給往左子樹走的函式1，給右子樹走的函式-1 ，
用來代表下一層的時候拿來判定是不是左葉子的前置依據。
當我們看到from == 1且左右節點均為NIL時，
就可以將當前的節點值回傳，
否則的話，就繼續遞迴往下找底下子樹當中左葉的和。
依此，寫成程式碼如下：
Java
Java的部分，每次先檢查root是否為null，
接著我們的答案就用
sumOfLeftLeaves(root.left, 1) + sumOfLeftLeaves(root.right, -1)
來取得。
其他的寫法概念如前所述。
Python
Python的部分寫一個子函式，因為這邊沒有用self，
所以可以不用self.getSum來算。
(也可以把add設定預設値-1，
使用單個sumOfLeftLeaves來解此題，
這個化簡方式很簡單，就留給讀者來練習看看XD)
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(N)/O(1)，因為要經過每個節點，
而如果考慮call stack的話，
空間複雜度會是O(depth of Tree))
相似及延伸
0235. Lowest Common Ancestor of a Binary Search Tree (Easy)
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~
另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve