在Python中计算二叉树的深度

Question

我刚开始学习编程，想用Python来计算二叉树的深度。我觉得我出错的原因是因为深度是Node类的一个方法，而不是一个普通的函数。我正在学习面向对象编程（OOP），希望能用一个方法来实现。这可能是个新手错误……

这是我的代码：

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

Answer 1

你需要考虑四种情况：

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

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

Answer 3

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>；如果 <some condition> 为假（被当作假），就返回 <otherwise>。