劍指 Offer 34. 二叉樹中和為某一值的路徑

難度中等322

給你二叉樹的根節(jié)點(diǎn) root 和一個(gè)整數(shù)目標(biāo)和 targetSum ，找出所有 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 路徑總和等于給定目標(biāo)和的路徑。

葉子節(jié)點(diǎn) 是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例 1：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

輸出：[[5,4,11,2],[5,8,4,5]]

。

#?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:?TreeNode,?target:?int)?->?List[List[int]]:

????????res=[]

????????path=[]

????????def?judgeCur(root,target):

????????????if?not?root:return

????????????path.append(root.val)

????????????target-=root.val

????????????if?target==0?and?not?root.left?and?not?root.right:

????????????????tmp=path[:]

????????????????#如果不復(fù)制的話，path改變了,res里面的也會(huì)改變

????????????????res.append(tmp)

????????????judgeCur(root.left,target)

????????????judgeCur(root.right,target)

????????????path.pop()

????????judgeCur(root,target)

????????return?res