类型错误：解包元组递归函数调用

Question

我有以下代码：

def myCalculation(self, root, max_val): 
        
        if root == None:
            return -1
        
        LH = 1 + (self.myCalculation(root.left, max_val))[0]
        RH = 1 + (self.myCalculation(root.right, max_val))[0]
        
        ret = LH+RH
        
        if max_val < ret:
            max_val = ret
            
        return (max(LH, RH), max_val)

在这里，我返回两个值，因为对于堆栈上的最后一个函数调用以退出函数，必须将max_val返回到调用函数。因此，当函数的第三和第4个可执行行中，我进行函数调用并尝试使用返回值时，它给出了下方的typeerror。

错误是：

> TypeError: 'int' object has no attribute '__getitem__'

完整的追溯：

TypeError: 'int' object has no attribute '__getitem__'
    LH = 1 + (self.myCalculation(root.left, max_val))[0]
Line 14 in myCalculation (Solution.py)
    LH = 1 + (self.myCalculation(root.left, max_val))[0]
Line 14 in myCalculation (Solution.py)
    LH, max_val1 = 1 + self.myCalculation(root.left, 0)
Line 32 in diameterOfBinaryTree (Solution.py)
    ret = Solution().diameterOfBinaryTree(param_1)
Line 67 in _driver (Solution.py)
_driver()

第77行（solution.py）

我无法弄清楚递归中包装和解开包装的问题是什么？

Answer 1

问题是您的基本情况返回一个单个值。不过，您可以通过消除返回多个值和额外参数 max_val 的需要来简化算法。我们可以计算树的直径，t -

def diameter(t):
  if not t:
    return 0
  else:
    return max(                            # return maximum of:
      diameter(t.left),                    # diameter of left
      diameter(t.right),                   # diameter of right
      1 + height(t.left) + height(t.right) # or diameter of t itself
    )

其中树的高度，t定义为-

def height(t):
  if not t:
    return 0
  else:
    return 1 + max(height(t.left), height(t.right))

您可以在 Solution 类中编写 myCalculation -

class Solution:
  def myCalculation(self, root):
    return diameter(root)

因为 height 将在子节点上被多次调用，所以可以使用 lru_cache，有效地“记忆”功能 -

from functools import lru_cache

@lru_cache
def height(t):
  # ...