LeetCode面试题34.二叉树中求和到某个值的路径[剑指Offer][Medium][Python]】【回溯】问题是输入一棵二叉树和一个整数，打印出所有二叉树中节点值之和为输入整数的路径。从树的根节点向下到叶节点经过的节点形成一条路径。示例：给定以下二叉树，目标和=22,5/\48//\11134/\/\7251返回：[[5,4,11,2],[5,8,4,5]]提示：总节点数<=10000注：本题与主站113题相同。思路是回头遍历二叉树，以便记录路径。符合条件者加入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
