python - 总结二叉树中的节点深度

Question

为了总结任何给定二叉树中所有节点的深度，我编写了以下递归算法：

def nodeDepths(root):
    final=0
    helper(root,0,final)
    return final

def helper(node,d,final):
    if not node:
        return 
    final+=d
    helper(node.left,d+1,final)
    helper(node.right,d+1,final)

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

我的想法是：当我看到每个节点时，将该节点的深度添加到最终总和中，然后递归调用左右，以便它们可以做同样的事情。在递归调用堆栈的末尾，最终总和应该具有正确的值。

实际结果：最终总和始终为 0。

为什么这不起作用？

标签： pythonrecursionbinary-tree

Answer 1

Python 通过assignment传递它的参数。因此，如果将列表而不是变量传递给上面的方法，它将像这里一样工作：

def nodeDepths(root):
    final=[0]
    helper(root,0,final)
    return final[0]

def helper(node,d,final):
    if not node:
        return 
    final[0]+=d
    helper(node.left,d+1,final)
    helper(node.right,d+1,final)

简单来说，

• 如果传入一个可变对象，则可以对其进行更改，但如果将其分配给，则外部变量将不会反映更改。
• 如果传入不可变对象，则无法更改，并且外部变量不会反映更改。