1 題目描述

2 解題思路

2.1BFS 廣度優先搜索

我們設計一個這樣的隊列

隊列的每個元素是一個三元數組：從根節點到當前點的路徑總和+當前節點+從根節點到當前節點的路徑

每次我們從隊列中彈出一個元素的時候，我們考慮這個元素所對應的節點是不是葉子節點，如果是的話，判斷當前路徑總和是否是我們的target。如果是，將這一組路徑加到要返回的列表中；如果不是，什么也不做

否則，看此節點有沒有左右兒子節點，有的話，將對應的元素送入隊列

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:if(root==None):return Nonetmp=[[root.val,root,[root.val]]]ret=[]while(tmp):x=tmp.pop(0)if(x[1].right==None and x[1].left==None):#判斷是否是葉子節點print(x)if(x[0]==targetSum):#判斷葉子節點的路徑總和是否是targetret.append(x[2])elif(x[1].right==None):tmp.append([x[0]+x[1].left.val,x[1].left,x[2]+[x[1].left.val]])elif(x[1].left==None):tmp.append([x[0]+x[1].right.val,x[1].right,x[2]+[x[1].right.val]])else:tmp.append([x[0]+x[1].left.val,x[1].left,x[2]+[x[1].left.val]])tmp.append([x[0]+x[1].right.val,x[1].right,x[2]+[x[1].right.val]])#是否有左右兒子，有的話，將他們對應的元素加入隊列中return(ret)

?2.2 DFS深度優先遍歷

和BFS類似，DFS的參數也有三個

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:if(root==None):return Noneret=[]def dfs(val,node,lst):#print(val,node,lst)#print('\n')if(node.left==None and node.right==None and val==targetSum): ret.append(lst)elif(node.left==None and node.right==None and val!=targetSum):passif(node.right!=None):dfs(val+node.right.val,node.right,lst+[node.right.val])if(node.left!=None):dfs(val+node.left.val,node.left,lst+[node.left.val])dfs(root.val,root,[root.val])return(ret)

總結

以上是生活随笔為你收集整理的文巾解题 113. 路径总和 II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。