面试题：Java组合模式下的遍历策略及优化

高效遍历策略设计

深度优先遍历（DFS）：
- 递归实现：简单直观，适合内存消耗不敏感场景。对于树形结构，从根节点开始，递归访问每个子节点。

public class TreeNode {
    private List<TreeNode> children = new ArrayList<>();
    // 其他节点属性和方法

    public void dfsTraversal() {
        // 处理当前节点
        System.out.println("Visiting node: " + this);
        for (TreeNode child : children) {
            child.dfsTraversal();
        }
    }
}

- **栈实现**：对于大型树形结构，避免递归可能导致的栈溢出。使用栈来模拟递归过程。

import java.util.Stack;

public class TreeNode {
    private List<TreeNode> children = new ArrayList<>();
    // 其他节点属性和方法

    public void dfsTraversal() {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(this);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            // 处理当前节点
            System.out.println("Visiting node: " + this);
            for (int i = node.children.size() - 1; i >= 0; i--) {
                stack.push(node.children.get(i));
            }
        }
    }
}

广度优先遍历（BFS）：使用队列实现，按层遍历树形结构。有助于快速找到离根节点最近的符合条件的节点。

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

public class TreeNode {
    private List<TreeNode> children = new ArrayList<>();
    // 其他节点属性和方法

    public void bfsTraversal() {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(this);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 处理当前节点
            System.out.println("Visiting node: " + this);
            queue.addAll(node.children);
        }
    }
}

迭代器模式结合缓存：实现一个自定义迭代器，在迭代过程中缓存已经访问过的节点，避免重复访问。

import java.util.Iterator;
import java.util.Stack;

public class TreeNode implements Iterable<TreeNode> {
    private List<TreeNode> children = new ArrayList<>();
    // 其他节点属性和方法

    @Override
    public Iterator<TreeNode> iterator() {
        return new TreeNodeIterator(this);
    }

    private class TreeNodeIterator implements Iterator<TreeNode> {
        private Stack<TreeNode> stack = new Stack<>();
        private TreeNode lastReturned = null;

        public TreeNodeIterator(TreeNode root) {
            stack.push(root);
        }

        @Override
        public boolean hasNext() {
            return!stack.isEmpty();
        }

        @Override
        public TreeNode next() {
            TreeNode current = stack.pop();
            lastReturned = current;
            for (int i = current.children.size() - 1; i >= 0; i--) {
                stack.push(current.children.get(i));
            }
            return current;
        }

        @Override
        public void remove() {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            lastReturned.children.remove(lastReturned);
        }
    }
}

动态添加或删除节点处理

使用标志位：在节点类中添加一个标志位，如 isDeleted，在遍历过程中，当遇到标志位为 true 的节点时跳过它。添加节点时，直接将新节点按规则插入到树形结构中。

public class TreeNode {
    private boolean isDeleted = false;
    private List<TreeNode> children = new ArrayList<>();
    // 其他节点属性和方法

    public void setDeleted(boolean deleted) {
        isDeleted = deleted;
    }

    public boolean isDeleted() {
        return isDeleted;
    }

    public void addChild(TreeNode child) {
        children.add(child);
    }
}

基于版本号：为树形结构维护一个版本号，每次添加或删除节点时，版本号递增。遍历前记录当前版本号，遍历过程中如果版本号发生变化，重新开始遍历或者采用补偿机制（如记录变化节点，后续处理）。

public class Tree {
    private TreeNode root;
    private int version = 0;

    public void addNode(TreeNode node, TreeNode parent) {
        if (parent == null) {
            root = node;
        } else {
            parent.addChild(node);
        }
        version++;
    }

    public void removeNode(TreeNode node) {
        // 找到父节点并移除
        // 假设存在方法 findParent 找到父节点
        TreeNode parent = findParent(node);
        if (parent != null) {
            parent.children.remove(node);
            version++;
        }
    }

    public void traverse() {
        int startVersion = version;
        // 执行遍历操作
        // 如果遍历过程中 version != startVersion，处理方式如下
        if (version != startVersion) {
            // 重新遍历
            traverse();
        }
    }
}

使用写时复制（Copy - on - Write）策略：在遍历开始时，创建树形结构的一个副本。在遍历过程中，对副本进行操作，而原树形结构的修改不会影响遍历。遍历结束后，根据需要将修改合并回原树形结构。

import java.util.ArrayList;
import java.util.List;

public class TreeNode {
    private List<TreeNode> children = new ArrayList<>();
    // 其他节点属性和方法

    public TreeNode copy() {
        TreeNode copy = new TreeNode();
        for (TreeNode child : children) {
            copy.children.add(child.copy());
        }
        return copy;
    }
}

public class Tree {
    private TreeNode root;

    public void traverse() {
        TreeNode copyRoot = root.copy();
        // 对副本进行遍历操作
        // 如 DFS 遍历副本
        copyRoot.dfsTraversal();
    }
}

面试题：Java组合模式下的遍历策略及优化

知识考点

面试题答案

高效遍历策略设计

动态添加或删除节点处理