Leetcode 113. Path Sum II

题目：解法：类似backtracking

题目：

解法：类似backtracking

在path sum I的基础上稍作改动即可

class Solution: def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]: def helper(node,curr_sum,curr_path): if not node: return curr_path.append(node.val) if not node.left and not node.right and curr_sum+node.val==sum: ans.append(curr_path[:]) else: helper(node.left,curr_sum+node.val,curr_path) helper(node.right,curr_sum+node.val,curr_path) curr_path.pop() ans = [] helper(root,0,[]) return ans

C++版本：

class Solution { vector<vector<int>> ans; public: vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<int> curr_path; helper(root,0,curr_path,sum); return ans; } void helper(TreeNode* node, int curr_sum, vector<int> &curr_path,int sum){ if (!node) return; curr_path.push_back(node->val); if (!node->left && !node->right && curr_sum+node->val==sum){ ans.push_back(curr_path); }else{ helper(node->left,curr_sum+node->val,curr_path,sum); helper(node->right,curr_sum+node->val,curr_path,sum); } curr_path.pop_back(); } };

时间复杂度：O(nlogn). 对于每个节点，我们使用类似backtracking这种方式是只需要对每个节点访问一遍就可以的，但问题是还需要考虑将形成的path加入到最终答案的复杂度。每条path的长度应该等于树的深度也就是logn，而总共最多可能存在N/2条路径，所以复杂度是O(nlogn)