基于Python生成器的二叉搜索树(BST)高度方法实现求助

首先明确：计算BST高度的核心是基于节点的层级关系（当前节点到最远叶子节点的路径长度），和中序遍历的生成器逻辑完全无关——生成器只是用来输出有序节点序列的，它不会保留节点的层级信息，所以用生成器来实现height方法反而会绕远路。

最优实现：递归计算高度 #

这是最直接高效的方式，逻辑是：

• 空节点的高度定义为-1（这样叶子节点的高度为0，符合“路径长度”的定义）
• 非空节点的高度 = 1 + max(左子树高度, 右子树高度)

假设你的节点类和BST类基础结构如下：

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

    def inorder(self):
        # 你的中序遍历生成器
        if self.left:
            yield from self.left.inorder()
        yield self
        if self.right:
            yield from self.right.inorder()

class BST:
    def __init__(self):
        self.root = None

给Node和BST添加height方法：

class Node:
    # 保留原有__init__和inorder方法
    def height(self):
        left_h = self.left.height() if self.left else -1
        right_h = self.right.height() if self.right else -1
        return 1 + max(left_h, right_h)

class BST:
    # 保留原有__init__方法
    def height(self):
        return self.root.height() if self.root else -1

为什么不用生成器？ #

你的中序遍历生成器只会返回节点对象，没有任何关于节点所在层级、父节点的信息。如果硬要基于生成器实现height，你需要额外遍历所有节点并计算每个节点的深度（根到该节点的路径长度），然后取最大深度作为树的高度——这完全是多此一举，因为你需要额外的遍历逻辑来追踪深度，反而不如直接递归计算高效。

如果非要演示这种绕路的方式（仅作理解用，不推荐）：

class BST:
    # 保留原有方法
    def height_using_generator(self):
        if not self.root:
            return -1
        
        # 用栈迭代遍历，同时记录节点深度，复用中序遍历逻辑
        stack = [(self.root, 0, False)]
        max_depth = 0
        
        while stack:
            node, depth, visited = stack.pop()
            if visited:
                if depth > max_depth:
                    max_depth = depth
                continue
            
            # 中序遍历栈顺序：右-根-左（栈是后进先出）
            if node.right:
                stack.append((node.right, depth + 1, False))
            stack.append((node, depth, True))
            if node.left:
                stack.append((node.left, depth + 1, False))
        
        return max_depth

这个方法本质是把中序遍历的生成器逻辑改成迭代遍历，同时追踪深度，最终用最大深度作为树的高度（和递归实现的高度定义一致）。

内容的提问来源于stack exchange，提问作者Sandun Dayananda