删除 BST 中某个范围之间的叶节点

夏洛克

我想删除叶节点，其值超出给定范围（例如 [LR]）。我提出了一个解决方案，其中我只是遍历所有节点并检查当前叶节点的值是否在给定范围内。如果不是，那么我将删除此节点。

我的方法——

private static Node trim(Node root, int L, int R) {
    if (root == null)
        return null;

    if (root.left == null && root.right == null) {
        if (root.val < L || root.val > R)
            return null;
        else
            return root;
    }

    root.left = trim(root.left, L, R);
    root.right = trim(root.right, L, R);

    return root;
}

但这在 o(n) 中运行，因为我正在遍历所有节点（并且我没有在任何地方使用 BST 的属性）。谁能帮我找到更好/优化的解决方案？

图罗

就像 m.raynal 说的那样，因为你只想删除叶子，所以你不能比 O(n) 更好。

您只能在分支中的所有节点都在范围内时添加快捷方式，例如

private static Node trim(Node root, int L, int R) {

    return trim(root, L, R, null,null);
}

private static Node trim(Node root, int L, int R, Integer lBound, Integer rBound)
{
    if (root == null)
        return null;

    if (lBound != null && lBound >= L && rBound != null && rBound <= R ) {
        return root;
    }
    
    if (root.left == null && root.right == null) {
        if (root.val < L || root.val > R)
            return null;
        else
            return root;
    }

    root.left = trim(root.left, L, R, lBound , root.val);
    root.right = trim(root.right, L, R, root.val, rBound );

    return root;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。