带递归循环的分层元素删除算法：时间复杂度及替代方案咨询

Hey there! Let's break down your problem and answer your questions clearly.

Time Complexity Analysis #

First, let's talk about the time complexity of your recursive approach:

• If you use sets for to_delete and to_stay (so membership checks are O(1)), the overall time complexity is O(N), where N is the total number of elements across all nested levels. This is because every element (including sublists) is visited exactly once: we recursively process each sublist first (from the bottom up), then check each element in the current level to decide if it stays.
• If you use lists instead of sets for to_delete/to_stay, membership checks become O(M) (M being the size of the list), pushing the total complexity to O(N*M). So always convert these to sets first—it's a quick win for performance.

Feasible Alternative Approaches #

Your recursive method is totally valid, but here are some alternatives depending on your needs (like avoiding stack overflow for deeply nested lists, or writing more concise code):

1. Iterative Depth-First Search (DFS) #

Recursion can hit stack limits if your nested lists are extremely deep (like 10k+ levels). An iterative DFS uses a stack to simulate recursion, avoiding this issue while keeping the "bottom-up" processing order:

def filter_nested_iterative(lst, to_delete, to_stay):
    to_delete_set = set(to_delete)
    to_stay_set = set(to_stay)
    
    # Stack stores (current_list, parent_list, index_in_parent)
    stack = [(lst, None, None)]
    nodes = []
    
    # First pass: collect all nodes from top to bottom
    while stack:
        current, parent, idx = stack.pop()
        nodes.append((current, parent, idx))
        # Push sublists in reversed order to process them left-to-right later
        for i, item in enumerate(reversed(current)):
            if isinstance(item, list):
                stack.append((item, current, len(current)-1 - i))
    
    # Second pass: process nodes from bottom to top
    for current, parent, idx in reversed(nodes):
        filtered = []
        for item in current:
            if isinstance(item, list):
                filtered.append(item)  # Sublists are already processed
            else:
                if item not in to_delete_set or item in to_stay_set:
                    filtered.append(item)
        # Update the parent list or root
        if parent is None:
            lst = filtered
        else:
            parent[idx] = filtered
    return lst

2. Recursive List Comprehension (Concise Version) #

If your nested depth isn't extreme, you can simplify the recursive code with list comprehensions for cleaner syntax:

def filter_nested_comp(lst, to_delete, to_stay):
    to_delete_set = set(to_delete)
    to_stay_set = set(to_stay)
    return [
        filter_nested_comp(item, to_delete_set, to_stay_set) if isinstance(item, list) else item
        for item in lst
        if not (item in to_delete_set and item not in to_stay_set) or isinstance(item, list)
    ]

This does the same bottom-up processing but in a more compact way.

3. Generator-Based Traversal #

For very large nested lists, using a generator can save memory by processing elements on-the-fly instead of building a new list upfront:

def filter_nested_generator(lst, to_delete, to_stay):
    to_delete_set = set(to_delete)
    to_stay_set = set(to_stay)
    for item in lst:
        if isinstance(item, list):
            yield list(filter_nested_generator(item, to_delete_set, to_stay_set))
        else:
            if item not in to_delete_set or item in to_stay_set:
                yield item

# Usage: convert generator output to list
filtered_list = list(filter_nested_generator(original_list, to_delete, to_stay))

4. Bottom-Up BFS #

You can also use a BFS approach to first identify all levels from bottom to top, then process each level sequentially. This is useful if you need explicit control over which levels you're handling:

def filter_nested_bfs(lst, to_delete, to_stay):
    to_delete_set = set(to_delete)
    to_stay_set = set(to_stay)
    
    # Collect all levels (bottom to top)
    levels = []
    queue = [lst]
    while queue:
        current = queue.pop(0)
        levels.append(current)
        for item in current:
            if isinstance(item, list):
                queue.append(item)
    # Reverse to process from bottom up
    for level in reversed(levels):
        filtered = []
        for item in level:
            if isinstance(item, list):
                filtered.append(item)
            else:
                if item not in to_delete_set or item in to_stay_set:
                    filtered.append(item)
        # Replace the original level with filtered version
        level[:] = filtered
    return lst

Key Takeaways #

• Recursion is great for readability when nested depth is manageable.
• Iterative DFS is safer for deeply nested structures to avoid stack overflow.
• Always use sets for to_delete and to_stay to keep membership checks fast.

内容的提问来源于stack exchange，提问作者moe