获得 BST 中的下一个最高值

Question

我写了一个函数来获取二叉搜索树中的下一个最高值，如果输入值是树中最高的 return 0:

def getNext(root, x):
if x > root.d:
    if root.r == None:
        return 0
    else:
        if x > root.r.d:
            getNext(root.r, x)
        else:
            temp = root.r

            while temp.l != None:
                temp = temp.l

            return temp.d
else:
    if root.l == None:
        return root.d
    elif x < root.l.d:
        getNext(root.l, x)
    else:
        temp = Node('')
        temp = root.l.r #53

        if temp.d > x:
            getNext(temp, x)
        else:
            while temp != None:
                if temp.r == None:
                    return root.d
                elif x > temp.r.d:
                    temp = temp.r
                else:
                    getNext(temp.r, x)
                    break

但它只有 returns None

我试过在 return 之前添加一个打印件，打印件实际上输出正确

Answer 1

在每次递归调用前加一个return，即

return getNext(root.r,x)

return getNext(root.l,x)

return getNext(temp,x)

return getNext(temp.r,x)

获得 BST 中的下一个最高值

get next highest value in BST

python

binary-search-tree