思路在递归的同时额外维护从根到当前节点的元素和sum。此外还要在递归函数的外部维护一个path列表记录从根到当前节点路径上的所有节点。一、递归逻辑1.如果当前的节点是空节点则直接返回。2.把当前的节点加入path同时sum减去当前节点的值sum初始为targetSum。3.如果当前的节点是叶子节点且sum 0那么就把路径path加入答案。4.否则继续递归左右子树。5.在递归返回之前把我们在递归开头加入的节点也就是当前path的最后一个节点从path中去掉恢复现场。为什么要这样呢这是因为当我们递归完左子树要递归右子树之前path中还保留着左子树的节点。如果不及时去掉的话会导致最终加到答案中的path既包含左子树的节点又包含右子树的节点这连“路径”都算不上。二、复杂度分析1.时间复杂度O(n^2)其中n是二叉树的节点个数。首先遍历所有节点的时间复杂度是O(n)因为每个节点恰好被访问一次。对于“一条链 完全二叉树”这样的“扫帚型”二叉树我们会在O(n)个叶子节点处都去复制长为O(n)的pathres.add(new ArrayList(path))所以总的时间复杂度为O(n^2)。2.空间复杂度O(n)返回值不计入。附代码class Solution { private ListInteger path new ArrayList(); private ListListInteger res new ArrayList(); public ListListInteger pathSum(TreeNode root, int targetSum) { dfs(root, targetSum); return res; } private void dfs(TreeNode root, int sum) { if (root null) { return; } path.add(root.val); sum - root.val; if (root.left null root.right null sum 0) { res.add(new ArrayList(path)); } else { dfs(root.left, sum); dfs(root.right, sum); } path.remove(path.size() - 1); } }