LeetCode打家劫舍III两段相似代码为何一段超时一段通过？

以下两段均为LeetCode中House Robber III的解法代码，一段是可通过的最优解，另一段会触发超时错误：

正确代码 #

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root:
                return [0,0]
            leftpair=dfs(root.left)
            rightpair=dfs(root.right)
            withroot=root.val+leftpair[1]+rightpair[1]
            withoutroot=max(leftpair)+max(rightpair)
            return [withroot,withoutroot]
                
        return max(dfs(root))          

超时代码 #

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root:
                return [0,0]
            
            left=root.val+dfs(root.left)[1]+dfs(root.right)[1]
            right=max(dfs(root.left))+max(dfs(root.right))
            return [left,right]
                
        return max(dfs(root))        

超时原因分析 #

两者的时间复杂度有本质差异，核心问题是重复递归调用：

• 正确代码对每个节点的左右子树仅调用一次dfs，将返回结果存入leftpair和rightpair变量，后续计算直接复用这两个结果。每个节点仅被访问一次，时间复杂度为O(n)（n为树的节点总数）。
• 超时代码中，计算left时调用dfs(root.left)[1]，计算right时又调用max(dfs(root.left))——这意味着对同一个root.left子树发起了两次完全独立的递归遍历，root.right同理也被递归两次。

这种重复调用会让时间复杂度指数级增长：最坏情况下（比如链式结构的二叉树），每个节点会被访问2^depth次，深度越深，重复次数爆炸式增加，最终导致超时。

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