多子树（ArrayList存子节点）遍历求助：通用实现及应用疑问

Hey there! Let's tackle your two questions clearly and walk through fixing that leaf collection code—no more hardcoded loops, promise!

Great question! This kind of multi-tree structure (where each node can have any number of children stored in a list like ArrayList) is super common in real-world code, not just exams. Here are a few examples:

• File systems: Every folder can have multiple subfolders or files—each folder is a node, and its children are the items inside it.
• DOM trees: HTML elements (like <div> or <ul>) can have multiple child elements, which are stored in a list-like structure under the parent node.
• Organization hierarchies: A company's org chart where each manager can have multiple direct reports.

Exams focus on it because it's a fundamental way to represent hierarchical data that's more flexible than binary trees (which only allow two children). So yes, you'll absolutely run into this in real projects!

First off: BFS and DFS aren't just for binary trees! They work perfectly for multi-tree structures—you just need to iterate through all children of a node instead of checking left/right. I know recursion can feel intimidating, but it's actually the most straightforward way to handle this kind of hierarchical data. Let's break this down.

The problem with your current code #

Your nested loops only handle trees up to 3 levels deep. If you have a tree with 4+ levels, it'll miss leaves deeper down. We need a way to handle any depth automatically.

Solution 1: Recursive DFS (simplest for this use case) #

Recursion lets us repeat the same logic for every node, no matter how deep it is. Here's a cleaned-up version:

public ArrayList<Integer> getLeafValues() {
    ArrayList<Integer> leafList = new ArrayList<>();
    collectLeaves(this, leafList);
    return leafList;
}

// Helper method to recursively collect leaves
private void collectLeaves(Tree node, ArrayList<Integer> leafList) {
    // If this node has no children, it's a leaf—add its data
    if (node.children.isEmpty()) {
        leafList.add(node.data);
        return;
    }
    // For each child node, recursively collect its leaves
    for (Tree child : node.children) {
        collectLeaves(child, leafList);
    }
}

How this works:

1. We start with the root node (this) and pass along our empty leaf list.
2. For each node, we check if it's a leaf (no children). If yes, add its data to the list.
3. If not, we loop through all its children and run the same check on each one. This keeps going until we hit every leaf in the tree, no matter how deep.

Solution 2: Iterative DFS (no recursion) #

If recursion makes you nervous, we can use a Stack to mimic the recursive call stack manually:

import java.util.Stack;

public ArrayList<Integer> getLeafValues() {
    ArrayList<Integer> leafList = new ArrayList<>();
    Stack<Tree> stack = new Stack<>();
    stack.push(this);

    while (!stack.isEmpty()) {
        Tree currentNode = stack.pop();
        
        if (currentNode.children.isEmpty()) {
            leafList.add(currentNode.data);
            continue;
        }
        // Push children in reverse order to keep the same order as recursive DFS
        for (int i = currentNode.children.size() - 1; i >= 0; i--) {
            stack.push(currentNode.children.get(i));
        }
    }
    return leafList;
}

Solution 3: BFS (level-order traversal) #

If you want to collect leaves level by level (starting from the top), use a Queue instead of a stack:

import java.util.Queue;
import java.util.LinkedList;

public ArrayList<Integer> getLeafValues() {
    ArrayList<Integer> leafList = new ArrayList<>();
    Queue<Tree> queue = new LinkedList<>();
    queue.add(this);

    while (!queue.isEmpty()) {
        Tree currentNode = queue.poll();
        
        if (currentNode.children.isEmpty()) {
            leafList.add(currentNode.data);
            continue;
        }
        // Add all children to the queue to process next level
        for (Tree child : currentNode.children) {
            queue.add(child);
        }
    }
    return leafList;
}

All three solutions will work for any tree structure, no matter how many levels or children each node has.

Don't worry if recursion feels tricky at first—practice with small trees, and it'll click eventually. The key idea with multi-tree traversal is always the same: for every node, process it, then iterate through all its children and do the same.

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