0

我正在尝试解决以下问题:

返回二叉搜索树的根 t 修改为仅包含值 <= k。(使用正常的 BST 类,我们有一个项目,左右)

def prune(t,k):
    if not t:
        return None
    if k < t.item
        while t.item > k:
            t = t.left
    return t

我认为我做错了。也许有一些简单的递归方法可以做到这一点?

4

1 回答 1

0

我想你想要这样的东西:

def prune(t, k):
    if t is None or t.item > k:
        return None
    t.right = prune(t.right, k)
    return t

这是递归的,当它到达任何None节点或大于k. 由于这是一个 BST,t.item <= k意味着所有节点t.left也将是,所以我们可以忽略它们。

于 2014-04-15T22:49:05.853 回答