删除 BST 范围内的叶节点

Question

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

我的做法-

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 的属性）。谁能帮我找到更好/优化的解决方案？

Answer 1

就像 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;
}

删除 BST 范围内的叶节点

Delete leaf nodes between a range in BST

java

algorithm

binary-search-tree

tree-traversal