Leetcode之旅|從了解一棵樹開始（1）

---

題目描述

　　從這周開始做了點tree相關的題，發現遞歸和深度/廣度優先搜索(DFS/BFS)是繞不開的話題。對於遞歸，我還是沒能熟練操作，現在只能通過半參考別人的解答半練習的狀態來學習這類題目的解法。

　　今天的主題的Path Sum，就是給出一棵二叉樹，一個target數值，找出節點值之和等於target的路徑。按照難易程度，分為如下幾個level:

　　- 1.0版本：給出一棵樹，一個target值，從根節點(root)開始到葉子結點(leaves)結束，如果存在一個路徑，位於該路徑的所有節點的數值之和等於target，說明path存在，返回True;反之，返回False。

　　- 2.0版本：在1.0的基礎上，找出所有滿足的路徑，並將每個符合要求的路徑的節點值以列表形式返回。

　　- 3.0版本： 在上述兩個版本的基礎上，不限於從root節點開始，也不限於到leaves節點結束，找出所有滿足要求的路徑數。

　　比如，對如下一棵二叉樹和target = 22：

5 / 4 8 / / 11 13 4 / 7 2 1

　　- 1.0版本：返回True，因為存在root-to-leaf路徑5->4->11->2，其節點值之和等於target=22。

　　- 2.0版本：返回[[5,4,11,2],[5,8,4,5]]。

　　- 3.0版本：返回3，因為存在三條路徑：

　　1. 5->4->11->2;

　　2. 4->11->7;

　　3. 8->13。

　　

---

　　　　　　　　　　　解題思路

---

1.0版本

　　從二叉樹的形狀就可以看出，和tree相關的題目會很直觀地想到遞歸，因為從根節點開始，以它的左節點或者右節點(存在且不為leaf)為根節點的話依然是一棵樹。同時，這道題也很容易讓人想到leetcode的入門第一題：twosum。所以這道題我們可以按照如下思路遞歸：

　　- 根節點為null：返回False;

　　- 根節點不為null且存在左/右:遞歸調用hasPathSum函數，其中傳遞參數root改為root.left和root.right，target改為target-root.val,左右的返回值邏輯為or (遞推關係);

　　- 如果根節點值等於target值，說明路徑存在，返回True(出口條件)。

---

　　代碼如下：

1.0版本代碼

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def hasPathSum(self, root, target): """ :type root: TreeNode :type sum: int :rtype: bool """ if not root: return False if root.left or root.right: return self.hasPathSum(root.left,target-root.val) or self.hasPathSum(target.right,sum-root.val) return root.val==sum

---

2.0版本

　　這道題我一開始就否認了直接遞歸，覺得很難寫，後來看到discuss說是用DFS，覺得挺好。下面的解析思路和代碼希望我能學習並運用好。

　　簡而言之，利用DFS，所以本質上還是遞歸的，遞歸思路如下：

• 設定全局變數res以存儲結果，而且dfs函數是沒有返回值的，只是在遞歸調用過程中對res進行修改，最後在主程序中返回。這種情況其實可以直接在主函數里將dfs寫成方法。另外，只在根節點不為null的時候，dfs函數會有操作。
• dfs傳遞的參數有root,target,path,res,其中root,target會在遞推關係中更改，而path值會記錄訪問路徑。
• 當節點值等於target且它沒有左右孩子時(說明為leaf)，說明該路徑滿足條件，則將該節點加入路徑，而該路徑加入res。
• 遞推關係：root->root.left/root.right,target->target-root.val，path->path+[root.val],res按實際情況決定是否更新。

---

　　代碼如下：

2.0版本代碼

class Solution: def pathSum1(self, root, target): """ :type root: TreeNode :type sum: int :rtype: List[List[int]] """ if not root: return [] res = [] self.dfs(root,target,[],res) return res def dfs(self,root,target,path,res): if root: if root.val==target and not root.left and not root.right: res.append(path+[root.val]) self.dfs(root.left,target-root.val,path+[root.val],res) self.dfs(root.right,target-root.val,path+[root.val],res)

　　記得當時學演算法課的時候，dfs和bfs都是通過stack實現的，所以我們可以不需要遞歸，而是藉助stack來實現。這樣演算法的效率明顯提升(時間縮短20%)。

　　為啥stack可以實現呢？因為我們用堆棧不僅記錄的節點，同時記錄了當前節點的歷史訪問路徑。而當我們每訪問一個節點，只需要將其入棧，且在其之前訪問過的節點已經計入了path。而當檢驗路徑是否滿足需求時，節點和以該節點為終點的路徑會出棧。如果符合，則納入res；如果不符合，則繼續往下走(深度優先)。

　　發現這段寫得不太好，可能是因為我理解得還不夠透徹，接下來這個部分要加強練習。

---

2.0 版本 stack代碼

class Solution: def pathSum2(self, root, target): """ :type root: TreeNode :type sum: int :rtype: List[List[int]] """ if not root: return [] res = [] # 用stack記錄當前根節點，和值，以及路徑 stack = [(root,root.val,[root.val])] while stack: cur, cur_sum,cur_path = stack.pop() if not cur.left and not cur.right and cur_sum==target: res.append(cur_path) if cur.left: stack.append((cur.left,cur_sum+cur.left.val,cur_path+[cur.left.val])) if cur.right: stack.append((cur.right,cur_sum+cur.right.val,cur_path+[cur.right.val])) return res

---

3.0版本

　　3.0版本很有意思，竟然是easy級別的，但我用自己想到的方法跑太慢了，時間複雜度感覺應該是 ，所以跑了將近1 s，果不其然是墊底級別的。後來看到別人的dfs方法時間瞬間縮短到了95 ms，應該是hash的作用吧(小白不確定是不是這個原因？)。

　　先來看> 1000 ms的解法：運用了1.0版本的找路徑的方法，不過因為現在不限於是root-to-leaf，所以得遍歷所有的節點將其作為root，找到即計數加1。

3.0版本 慢速代碼

class Solution: def pathSum3(self, root, target): """ :type root: TreeNode :type sum: int :rtype: int """ if root: return self.hasPathSum(root,s)+self.pathSum(root.left,s)+self.pathSum(root.right,s) return 0 def hasPathSum(self,root,target): if root: return int(root.val==s)+self.hasPathSum(root.left,s-root.val)+self.hasPathSum(root.right,s-root.val) return 0

　　加速版解法很有意思，採用的字典dict這一數據結構，用來存儲當前訪問路勁節點的和值。判斷的方法也機智(真是沒想到)，即將每次採集到的和值減去target，如果這個鍵值存在，說明該鍵值存儲的路徑的終點到目前節點的"距離"即為target (再一次體會到智商被虐的痛楚)。

　　這版本解法的另一特點是運用dfs，可見以後解題得形成這種思維習慣：什麼樣類型的問題可以化為dfs的問題？

---

3.0加速版代碼

class Solution: def pathSum4(self, root, target): """ :type root: TreeNode :type sum: int :rtype: int """ if not root: return 0 # 屬性值，記錄符合要求的路徑數目，可以在dfs中更改 self.count = 0 # 記錄已訪問的路徑的和值 # 鍵值不存在或0表示不曾出現，為1表示出現過 # 只有0和1兩個值(暫時不明白這麼說是否正確) dic = {0:1} self.dfs(root,s,0,dic) return self.count # dfs的四個參數： # node:當前訪問節點 # target：目標值 # cur_sum：當前路徑和值 # dic:路徑和值字典 def dfs(self,node,target,cur_sum,dic): if node: # 上一輪和值與當前節點值相加更新為此輪和值 cur_sum += node.val # 如果存在與此輪和值「距離」為target的鍵值，count+1 self.count += dic.get(cur_sum-target,0) # 將此輪和值存入字典，次數加1 dic[cur_sum] = dic.get(cur_sum,0)+1 # 左右孩子遞歸 self.dfs(node.left,s,cur_sum,dic) self.dfs(node.right,s,cur_sum,dic) # 遞歸結束後此輪和值次數清空，因為要開始新的路徑記錄和判斷了 dic[cur_sum]-=1

---

總結

　　太虐了！！！不過我感覺為了熟練操作二叉樹，首先應該熟悉的是操作這類數據結構的方法，目前我理解的主要是遞歸和DFS/BFS，所以對應的應該對使用stack(可能還有dic)都能很熟悉，因為很多時候使用stack會出現邏輯銜接不上或者出口甚至是入口條件找不對等等。

　　無論如何，努力吧。

　　嗯。

推薦閱讀：