recursion - BST中序递归：找到大于K的第一个节点

Question

我的代码似乎一直运行到最后（因此返回 None），而不是在找到子树时停止。

def first_greater_than_k(tree, k):
    if not tree: 
        return None

    first_greater_than_k(tree.left, k)

    if tree.data > k:
        return tree
        
    first_greater_than_k(tree.right, k)

标签： recursionbinary-search-treetree-traversalinorder

Answer 1

没有递归的原始答案：

def first_greater_than_k(tree, k):
    subtree, first_so_far = tree, None

    while subtree:
        if subtree.data > k:
            first_so_far, subtree = subtree, subtree.left
        else:
            subtree = subtree.right
    
    return first_so_far