用Python计算二叉树的深度

Question

我是编程新手，正在尝试在Python中计算二叉树的深度。我认为我的错误是因为深度是Node类的一个方法而不是常规函数。我想学习面向对象编程，并希望使用一个方法。这可能是初学者的错误......以下是我的代码：

class Node:

    def __init__(self, item, left=None, right=None):
        """(Node, object, Node, Node) -> NoneType
        Initialize this node to store item and have children left and right.
        """
        self.item = item
        self.left = left
        self.right = right

    def depth(self):
        if self.left == None and self.right == None:
            return 1

        return max(depth(self.left), depth(self.right)) + 1

i receive this error:

>>>b = Node(100)

>>>b.depth()

1 

>>>a = Node(1, Node(2), Node(3))

>>>a.depth()

Traceback (most recent call last):
  File "C:\Program Files\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line 1, in <module>
    # Used internally for debug sandbox under external interpreter
  File "C:\Program Files\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line 15, in depth
builtins.NameError: global name 'depth' is not defined

- user2133075

---

+1 是针对您问题的正确直觉。 - Ray Toal

供将来参考，我认为 new bee 应该拼作 newbie，如果我没记错的话。 - Snakes and Coffee

直觉部分正确（将depth()作为方法调用解决了问题），但还不完整。解释为什么您无法从内部访问该方法，而使用常规函数可以的根本原因是Python中作用域和类定义如何工作的某些细节。当您调用常规模块级函数时，其“全局”作用域将是包含此函数的模块。但是，在创建类型对象后，可以认为定义方法的作用域已被丢弃。 - millimoose

顺便提一下，根据PEP 8的建议，你应该总是使用self.left is None而不是self.left == None。这可以保护你免受糟糕设计的类的影响，并提高性能，但真正的原因是"is None"是Pythonic的一种方式，使有经验的Python程序员更容易读懂你的代码。 - abarnert

Answer 1

def depth(self):
    if self.left == None and self.right == None:
        return 1

    return max(depth(self.left), depth(self.right)) + 1

应该是

def depth(self):
    return max(self.left.depth() if self.left else 0, self.right.depth() if self.right else 0) + 1

更易读的版本：

def depth(self):
    left_depth = self.left.depth() if self.left else 0
    right_depth = self.right.depth() if self.right else 0
    return max(left_depth, right_depth) + 1

问题在于没有 depth 函数。它是 Node 对象的一个方法，因此您需要从对象本身（左和右）调用它。我缩短了代码为 self.left.depth() if self.left else 0 和 self.right.depth() if self.right else 0，以去除之前的检查（它们现在是隐式的），因为我认为左边可能是 None 而右边是 Node 或反过来，这将导致原始代码抛出 AttributeError，因为 None 没有一个名为 depth 的方法。

编辑：

回答关于 <something> if <some condition> else <otherwise> 块的问题：

如果 <some condition> 是真值（视为真），则该行给出 <something>，否则给出 <otherwise>。

- Snakes and Coffee

---

把它压缩成一行有点难以阅读，但这是正确的答案。 - Hamish

@Marius：不，默認情況下返回對象本身，在布爾上下文中為真，因此self.left是self.left is not None的有效測試。 - abarnert

@Hamish，我已经重新编写了更易读的形式。感谢您的建议。 - Snakes and Coffee

PS，@SnakesandCoffee：很好的解释为什么不能只做 if self.left is None and self.right is None。如果OP想要保留结构不变，他还必须编写类似于 elif self.left is None: return self.right.depth()+1 和 elif self.right is None: return self.left.depth()+1 的内容。因此，我认为你的版本更易读。 - abarnert

如果您认为这个答案是正确的，请点击投票旁边的绿色勾号（这会给我15个声望和您2个声望）。@user2133075 - Snakes and Coffee

Answer 2

为了清晰起见，我建议您将depth方法编写成这样：

def depth(self):
    current_depth = 0

    if self.left:
        current_depth = max(current_depth, self.left.depth())

    if self.right:
        current_depth = max(current_depth, self.right.depth())

    return current_depth + 1

- Wolph

---

为了清晰起见，建议在方法名和其中的局部变量中不要使用相同的名称。 - millimoose

所有节点的深度都是1吗？为什么这样做？ - Hyperboreus

@Hyperboreus：这基本上就是他的代码在做什么，我没有检查正确性。只是给出了一个更易读的模式 :) - Wolph

@millimoose：好的，没问题，我会改的 :) - Wolph

但是你为什么想要故意发布错误的代码呢？无论是问题还是其他答案都在递归中加1。 - Hyperboreus

问题已经修改，我的代码反映了原始代码的工作版本。我没有检查它的正确性。 - Wolph

Answer 3

错误来自于这一行：

return max(depth(self.left), depth(self.right)) + 1

你正在使用深度作为一个函数，并试图将其应用于左右节点。因为左右节点也是节点，它们具有深度方法。

你应该像这样调用深度方法：

return max(self.left.depth(), self.right.depth()) + 1

自变量被隐式地传递给深度方法，但使用点运算符将其与Python一起使用时，告诉Python该方法属于Node实例，而不是未绑定到对象的其他函数。

- munk

Answer 4

你需要考虑四种情况：

1. 两个子树都为空。
2. 只有左子树为空。
3. 只有右子树为空。
4. 两个子树都不为空。

你已经涵盖了1和4的情况，但是忽略了2和3。 解决方法:

# Return height of tree rooted at this node.
def depth(self):
    if self.left == None and self.right == None:
        return 1
    elif self.left == None:
        return self.right.depth() + 1
    elif self.right == None:
        return self.left.depth() + 1
    else:
        return max(self.left.depth(), self.right.depth()) + 1

- E.T.