刷题|【剑指 Offer】剑指 Offer 34. 二叉树中和为某一值的路径 leetcode|深度优先|leetcode|算法

题目
代码
执行用时：32 ms, 在所有 Python3 提交中击败了98.76% 的用户
内存消耗：16.5 MB, 在所有 Python3 提交中击败了59.19% 的用户
通过测试用例：114 / 114

class Solution: def dfs(self,root,target): if not root: return self.ans.append(root.val) if (not root.left and not root.right) and sum(self.ans)==target: self.rs.append(self.ans.copy()) self.dfs(root.left,target) self.dfs(root.right,target) self.ans.pop() def pathSum(self, root: TreeNode, target: int) -> List[List[int]]: self.rs=[] self.ans=[] self.dfs(root,target) return self.rs

【方法2】
执行用时：40 ms, 在所有 Python3 提交中击败了82.24% 的用户
内存消耗：16.4 MB, 在所有 Python3 提交中击败了85.98% 的用户
通过测试用例：114 / 114

class Solution: def dfs(self,root,target): if not root: return self.ans.append(root.val) target-=root.val if (not root.left and not root.right) and target==0: self.rs.append(self.ans.copy()) self.dfs(root.left,target) self.dfs(root.right,target) self.ans.pop() def pathSum(self, root: TreeNode, target: int) -> List[List[int]]: self.rs=[] self.ans=[] self.dfs(root,target) return self.rs

【刷题|【剑指 Offer】剑指 Offer 34. 二叉树中和为某一值的路径】【方法3】
执行用时：40 ms, 在所有 Python3 提交中击败了82.24% 的用户
内存消耗：16.2 MB, 在所有 Python3 提交中击败了95.29% 的用户
通过测试用例：114 / 114

class Solution: def pathSum(self, root: TreeNode, target: int) -> List[List[int]]: if not root:return [] node_pa=dict() node_pa[root]=None queue=[root] ans=[] while queue: root=queue.pop(0) if root.left: node_pa[root.left]=root queue.append(root.left) if root.right: node_pa[root.right]=root queue.append(root.right) if not root.left and not root.right: temp=[root.val] while root: temp.append(root.val) root=node_pa[root] temp=temp[::-1][:-1] if sum(temp)==target: ans.append(temp) return ans