python - 二叉搜索树查找最小值不清楚

Question

我试过的逻辑：

 def min_tree_value(self):
        
       while self.left:
            self.left = self.left.left
        
        return self.data 

实际Python程序逻辑：

def min_tree_value(self):
        if self.left is None:
            return self.data
        
        return self.left.min_tree_value()

实际的 Python 程序逻辑是递归形式的。我在 While loop() 中尝试了相同的逻辑

我不确定我的逻辑是否正确。请帮助我找出不正确的逻辑并指出我错了。

标签： pythonalgorithmdata-structuresbinary-search-tree

Answer 1

您的逻辑几乎就在那里，但不完全是：

def min_tree_value(self):
    node = self
    while node.left:
        # don't change the structure by rebinding node.left,
        # but iterate the tree by moving along nodes!
        node = node.left  
    return node.data 

请注意，在原始代码中，您self在返回其值之前永远不会重新分配，因此您始终返回根值。