從LeetCode學演算法 - 103 Tree (16) / DFS (13) / BFS (3) / Queue (4)

0112. Path Sum (Easy)

寫在前面

容筆者工商一下， 「從Leetcode學演算法｜進階篇」及 加贈的**「從Leetcode學演算法｜面試篇」已經全數上傳完囉！**

目前只剩下給讀者的進階篇+面試篇(3150) 和全套同捆優惠(3990) 了QQ
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」：
https://bit.ly/leetcodeadv
「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/leetcodeall

內容介紹：
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

Question

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exists a root-to-leaf path 5->4->11->2 which sum is 22.

分析/解題

給定一棵二元樹，試決定該二元樹是否有一個從根到葉的路徑，
使得路徑上的節點總和恰等於給定的目標和。

這一題是一整組Path Sum系列題的第一題，
除了接下來幾篇會陸續談到系列題外，這篇也想著重給讀者一個提醒：
很多時候能用DFS解的題目，通常也能用BFS解 (反之亦然)

所以當下遇到一個題目的時候，除非有限定要求，
否則只要能想到的解法就是好解法 ，
不要硬逼自己一定要用DFS或一定要用BFS。
(練習的時候，當然還是可以自我挑戰兩種都想出解來就是了XD)

首先我們要留意到一件事情：
由於是從根到葉，
所以我們只需要在走到左右均無節點時再檢查總和是否相符即可，
千萬不要沿途檢查呀XD！

再者，由於路途經過的都會算做計入的總和，
所以我們可以沿路將往下走所需的總和減去當前經過的節點。

依照這個概念，我們可以蠻直觀地寫出一個DFS的解：

先檢查root如果是NIL -> 直接回傳False
檢查root.left/root.right 是不是都為NIL -> 若均為NIL，
若root.val等於所需和 則回傳True ，否則回傳False
將往下走的剩下的和next定為sum — root.val(剩下需要湊的和)
回傳hasPathSum(root.left, next) || hasPathSum(root.right, next) (因為只要存在一條路徑即為True，所以兩者用或來連接)

由上可知，用來判定這個位置能不能成為我們要的路徑和，
只取決於兩點：

現在這個位置是否已經是葉(leaf)
現在這個位置的値是否是剩下需要的和

所以我們也可以用BFS的方式，搭配前面講過的Queue來處理：

同樣先檢查root及處理回傳
將**[(root, sum - root.val)]** 放入Queue當中
進行迴圈，每次從Queue中取出一組**(curr, val)** 並檢查：
3–1. 若curr.left/curr.right均為NIL -> ** 若val為0，回傳True**
3–2. 檢查curr.left，若存在 -> 將**(curr.left, val - curr.left.val)放入Queue** 中
3–3. 對curr.right做相同處理
若迴圈結束仍未回傳，則回傳Fals e(找不到適合的路徑)

依上面的方式，我們分別在Java/Python演示不同的方法：
(讀者也可以自行嘗試完整練完單一語言的DFS/BFS的方法)

Java

Java的部分，使用了DFS，所以整體而言看起來很簡單，
不過原則上有用遞迴的題目，就盡量要留意call stack的深度會不會超過。

Python

Python的部分則使用了BFS，搭配deque做為queue使用，
留意當val != 0的時候記得要繼續操作，因為你可能會有其他節點符和XD，
這點和DFS時不一樣，請特別留意不要直接在那邊回傳False呦！

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

「時間/空間複雜度？」
(O(N)/O(log N)或O(N)(平均)，
因為DFS的話記憶體計算call stack深度，
BFS的話則是要用最底部的橫向長度來看；
如果極端的狀況的話DFS也有可能到O(N)，因為樹可能不平衡)

相似及延伸

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

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

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