含字符串拼接的递归时间复杂度分析——LeetCode #1022解法疑问

你的分析完全正确，这个解法的时间复杂度确实是 O(NH)（其中N是树的节点总数，H是树的高度）。

具体原因： #

• 首先，dfs函数会被调用N次，每个节点恰好被访问一次。
• 每次调用里的字符串拼接path + str(root.val)是线性时间操作：对于深度为k的节点（根节点深度为0），path的长度是k，拼接后的字符串长度是k+1，所以单次拼接的时间是O(k+1)。最坏情况下（比如树是一条单链，H=N），所有节点的拼接操作总时间是1+2+...+N = N(N+1)/2，也就是O(N²)，对应O(NH)的上限。
• 另外，叶子节点处执行的int(path + str(root.val), 2)操作，同样需要遍历长度为H的字符串来转换为整数，这部分也是O(H)的时间，会进一步叠加到总时间里。

优化建议：避免字符串拼接，用数值累加降复杂度 #

可以不用字符串记录路径，而是直接用数值递推的方式，把时间复杂度降到 O(N)：

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        self.total = 0
        
        def dfs(node, current_val):
            if not node:
                return
            # 二进制路径数值递推：当前值左移一位（乘2）加当前节点值
            current_val = current_val * 2 + node.val
            # 到达叶子节点，累加结果
            if not node.left and not node.right:
                self.total += current_val
                return
            dfs(node.left, current_val)
            dfs(node.right, current_val)
        
        dfs(root, 0)
        return self.total

这个优化的核心是：每次递归传递的是当前路径对应的十进制数值，所有操作都是O(1)级别的，每个节点只需要一次计算，总时间复杂度直接降到O(N)，同时也节省了字符串拼接带来的额外空间开销。

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