LeetCode - 解题笔记 - 113 - Path Sum II

本题是 0112. Path Sum 的进一步扩展，前一个题只需要对状态进行回溯，本题需要回溯路径，和之前做过的DFS是类似的

• 时间复杂度： O ( N ) O(N) O(N)，其中 N N N为树中的节点个数，搜索算法，所有节点遍历一次
• 空间复杂度： O ( N ) O(N) O(N)，其中 N N N为树中的节点个数，受调用函数栈深度影响，平均情况为 O ( log ⁡ N ) O(log N) O(logN)，最坏情况为 O ( N ) O(N) O(N)

class Solution {
public:
    vector> pathSum(TreeNode* root, int targetSum) {
        vector> ans;
        vector path;
        this->findPath(root, path, ans, targetSum);
        
        return ans;
    }
    
private:
    void findPath(TreeNode* node, vector& path, vector>& ans, int sumNow) {
        if(node == nullptr) {
            return; // 缺省情况
        }
        
        path.push_back(node->val);
        if (node->left == nullptr && node->right == nullptr && sumNow - node->val == 0) {
            ans.push_back(path);
        }
        
        this->findPath(node->left, path, ans, sumNow - node->val);
        this->findPath(node->right, path, ans, sumNow - node->val);
        
        path.pop_back();
        
        return;
    }
};

Solution 1的Python实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        
        ans, path = list(), list()
        def findPath(node: Optional[TreeNode], sumNow: int) -> bool:
            if node is None:
                return
            
            path.append(node.val)
            if node.left is None and node.right is None and sumNow == node.val:
                ans.append(deepcopy(path))
        
            findPath(node.left, sumNow - node.val)
            findPath(node.right, sumNow - node.val)
            
            path.pop()
        
        findPath(root, targetSum)
        
        return ans