Got it, let’s work through this! You’ve nailed the recursive sum, and switching to iteration just means we need to manually manage the "to-process" nodes that recursion handles automatically with the call stack. The key difference from binary trees is that instead of dealing with separate left and right attributes, we have a whole list of children—which actually makes things easier, since we can just add all of them to our stack/queue in one go.

1. Depth-First Search (DFS) Iterative Approach #

This mirrors your recursive logic exactly, since recursion uses a depth-first traversal by default. We’ll use a stack to track nodes, popping the top node each time, adding its value to the total, then pushing all its children onto the stack.

class Node:
    def __init__(self, value, children):
        self.value = value
        self.children = children

def sumNodesIterDFS(root):
    total = 0
    stack = [root]  # Start with the root node in our stack
    
    while stack:
        current_node = stack.pop()  # Grab the top node from the stack
        total += current_node.value  # Add its value to the total
        
        # Reverse the children list to match the recursive traversal order (optional)
        # If you don't care about traversal order, you can skip reversed()—sum stays the same!
        stack.extend(reversed(current_node.children))
    
    return total

Why reversed()? Because stacks are LIFO (last-in, first-out). If we add children in their original order, the last child will be processed first. Reversing them makes the traversal order match your recursive function (processing the first child first), but since addition is commutative, the final sum will be identical either way.

2. Breadth-First Search (BFS) Iterative Approach #

If you prefer traversing level by level (instead of diving deep first), we can use a queue instead of a stack. This is great if you want to visualize the tree level by level, but again, the sum result is the same.

from collections import deque

def sumNodesIterBFS(root):
    total = 0
    queue = deque([root])  # Initialize queue with the root
    
    while queue:
        current_node = queue.popleft()  # Grab the front node from the queue
        total += current_node.value
        
        queue.extend(current_node.children)  # Add all children to the end of the queue
    
    return total

Queues are FIFO (first-in, first-out), so each node’s children are processed in the order they’re added, which means we traverse each level completely before moving down.

Testing with Your Example Tree #

Let’s verify both functions work with your sample tree:

exampleTree = Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])
print(sumNodesIterDFS(exampleTree))  # Output: 28
print(sumNodesIterBFS(exampleTree))  # Output: 28

Both give the same result as your recursive function—perfect!

Key Takeaway #

The core idea for iterative traversal (whether DFS or BFS) is:

• Use a container (stack/queue) to hold nodes you haven’t processed yet
• For each node you pull out, add its value to the total
• Add all of its children to the container to process next

Multi-node trees are actually simpler here than binary trees, because you don’t have to check for left and right separately—just extend your container with the entire children list.

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