14

我是编程新手，正在尝试在 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
4

4 回答 4

13 
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而右边是 aNode或反之亦然，这将导致原始代码抛出AttributeError因为没有None方法depth。

编辑

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

该行给出<something>if <some condition>is true-y（视为 true）和<otherwise>if <some condition>is false-y（视为 false）

于 2013-03-05T02:38:08.993 回答
4

为了清楚起见，我建议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
于 2013-03-05T02:41:28.943 回答
1

You've got four cases to consider:

  1. Both subtrees are empty.
  2. The left subtree alone is empty.
  3. The right subtree alone is empty.
  4. Neither subtree is empty.

You've covered cases 1 and 4, but missed 2 and 3. The fix:

# 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
于 2013-03-05T20:42:31.407 回答
1

错误来自这一行：

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

您将深度用作函数并尝试将其应用于左右节点。因为左右节点也是节点，所以有depth方法。

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

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

self 参数隐式传递给 depth 方法，但与点运算符一起使用它会告诉 Python 该方法属于 Node 实例，而不是未绑定到对象的其他函数。

于 2013-03-05T20:15:12.297 回答