计算二叉搜索树的节点时出错

Question

我正在尝试编写一个计算二叉搜索树节点数的函数。但是，当我执行该函数时，我得到了一个错误。这是错误：“非类型”对象没有属性“权限”。该错误适用于行p=p.right

如果需要提供更多数据，请告诉我

以下是函数：

def countelements(self, root):
    stack=[]
    p=root
    count=0
    while p!=None:
        stack.append(p)
        p=p.left
        count=count+1
    while (len(stack)>0):
        p=stack.pop()
        p=p.right
        while p!=None:
            p=p.left
            stack.append(p)
            count=count+1
            
    return count

Answer 1

我还没有仔细考虑您的核心逻辑，但是为什么在堆栈中存在None这个问题的根源必须是内部循环（参见下面的内联注释）

        while p!=None:
            p=p.left # But what if p.left is None?
            stack.append(p)
            count=count+1

Answer 2

使用递归数据结构（如二叉树）时，通常需要使用递归

def count_elements(root):
    if root is not None:
        left = count_elements(root.left)
        right = count_elements(root.right)
        return left + right + 1  # +1 for root itself
    else:
        return 0