力扣|其中每条路径的总和等于给定的总和。注意：叶子是没有子节点的节点。示例：给定下面的二叉树和总和=22,5/\48//\11134/\/\7251返回：[[5,4,11,2],[5,8,4,5]]问题扣给定一棵二叉树和一个目标和，求从根节点到叶节点的所有路径的和相等到给定的目标和路径。解释：叶节点是指没有子节点的节点。示例：给定以下二叉树，目标和=22,5/\48//\11134/\/\7251返回：[[5,4,11,2],[5,8,4,5]]思路是回头遍历二叉树，以便记录路径。符合条件者加入res。回溯记得删除当前节点。时间复杂度：O(n)，其中n是二叉树节点的数量。空间复杂度：O(n)，最坏情况下，二叉树退化为单向链表。Python3代码#定义二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defpathSum(self,root:TreeNode,sum:int)->List[List[int]]:res,path=[],[]#前序遍历：root左右defrecur(root,target):ifnotroot:returnpath.append(root.val)target-=root.val#查找路径如果target==0andnotroot.leftandnotroot.right:res.append(list(path))#复制一个路径添加到res中，这样修改路径不会影响resrecur(root.left,target)recur(root.right,target)#向上回溯，需要删除当前节点path.pop()recur(root,sum)returnresGitHublinkPython
