LeetCode 113. Path Sum II时间复杂度分析及优化方法问询

问题描述 #

我完成了LeetCode挑战113. Path Sum II：题目要求给定二叉树根节点和目标和targetSum，返回所有根到叶子节点的路径，路径节点值之和等于targetSum，路径以节点值列表形式返回。

我的JavaScript实现代码 #

var pathSum = function(root, targetSum) {
    let paths = [];
    if(root === null) {
        return [];
    }
    getAllSumPaths(root, [], paths, targetSum);
    return paths;
}; 

function getAllSumPaths(root, currPath, paths, targetSum) {
    if(root.left === null && root.right === null) {
        if(targetSum - root.val === 0) {
            currPath.push(root.val);
            paths.push([...currPath]);
            currPath.pop();
        }
        return;
    }
    currPath.push(root.val);
    if(root.left !== null){
        getAllSumPaths(root.left, currPath, paths, targetSum - root.val);
    }
    if(root.right !== null){
        getAllSumPaths(root.right, currPath, paths, targetSum - root.val);        
    }
    currPath.pop();
} 

疑问 #

我原本认为算法时间复杂度是O(n)（n为二叉树节点数），但因需要用扩展运算符复制有效路径到paths数组（避免后续pop操作修改已存入的路径），而该操作的时间复杂度为O(k)（k为路径长度），不确定如何计算整体时间复杂度，同时想了解是否有其他写法可避免该O(k)操作。

解答 #

时间复杂度分析 #

你的整体时间复杂度其实是O(n + L×k)，拆解来看：

• n是二叉树的总节点数，每个节点都会被遍历一次，这部分开销是O(n)；
• L是满足条件的根到叶子路径的数量，k是每条路径的平均长度。

极端场景下，比如满二叉树且所有路径都符合目标和，此时L等于叶子节点数（约n/2），每条路径长度k是O(logn)，整体复杂度会是O(n + nlogn)，也就是O(nlogn)；如果只有一条符合条件的路径，那复杂度就是O(n + k)，接近O(n)。

本质上，复制路径的开销是无法完全规避的——因为我们需要保存符合条件的路径，这些路径本身的总长度就是所有符合条件路径的节点数之和，这部分开销是必然存在的，只是实现方式不同而已。

避免显式回溯复制的写法 #

可以换一种递归思路，每次递归时创建新的路径数组，不用复用同一个currPath，这样就不需要回溯时的pop操作：

var pathSum = function(root, targetSum) {
    let paths = [];
    if (!root) return paths;
    
    function dfs(node, currentSum, currentPath) {
        // 到达叶子节点
        if (!node.left && !node.right) {
            if (currentSum + node.val === targetSum) {
                paths.push([...currentPath, node.val]);
            }
            return;
        }
        
        // 递归左子树，传递新的路径数组
        if (node.left) {
            dfs(node.left, currentSum + node.val, [...currentPath, node.val]);
        }
        // 递归右子树，传递新的路径数组
        if (node.right) {
            dfs(node.right, currentSum + node.val, [...currentPath, node.val]);
        }
    }
    
    dfs(root, 0, []);
    return paths;
};

这种写法虽然不用手动pop，但本质上还是会在递归传递时产生O(k)的复制开销，整体时间复杂度和你的原写法完全一致——不管是在叶子节点复制，还是在递归时复制，最终所有符合条件路径的总长度开销是相同的。

还有一种思路是把路径转成字符串暂存，最后再转回数组，但这种写法可读性差，而且字符串转数组的开销也不会比直接复制数组小，不推荐使用。

内容的提问来源于stack exchange，提问作者james