513 找树左下角的值
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
ret=''
h=0
def dfs(root,height):
if not root:
return
height+=1
dfs(root.left,height)
dfs(root.right,height)
nonlocal h,ret
if height>h:
h=height
ret=root.val
dfs(root,0)
return ret
112 路径总和
#递归
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return root.val==targetSum
return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)
113 路径总和 II
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
ret=[]
def dfs(r,p,t):
if not r:
return
p.append(r.val)
t=t-r.val
if not r.left and not r.right and t==0:
ret.append(p[:])
dfs(r.left,p,t)
dfs(r.right,p,t)
p.pop()
dfs(root,[],targetSum)
return ret
