Java树结构深度搜索：递归与迭代实现部门查找

import java.util.List;
import java.util.Optional;
import java.util.function.Predicate;

// 部门接口，定义了所有部门的基本属性
public interface Department {
    String getName();
    String getType();

    // 默认方法：检查当前部门是否匹配某个条件
    default Optional<Department> getMatchingDepartment(Predicate<Department> predicate) {
        if (predicate.test(this)) {
            return Optional.of(this);
        }
        return Optional.empty();
    }
}

// 公司接口，继承自部门，并拥有子部门列表，表示它是一个复合部门
public interface Company extends Department {
    List<Department> getDepartments();

    // 默认方法：尝试在子部门中查找匹配项
    // 注意：此实现仅检查直接子部门，且只返回第一个匹配项，不进行深度遍历
    default Optional<Department> getMatchingDepartment(Predicate<Department> predicate) {
        return getDepartments().stream()
                .map(department -> department.getMatchingDepartment(predicate))
                .filter(Optional::isPresent)
                .map(Optional::get)
                .findFirst();
    }
}

public interface Company extends Department {
    // ...
    default Optional<Department> getMatchingDepartment(Predicate<Department> predicate) {
        return getDepartments().stream()
                .map(department -> department.getMatchingDepartment(predicate)) // 对每个子部门调用其自身的getMatchingDepartment
                .filter(Optional::isPresent)
                .map(Optional::get)
                .findFirst(); // 找到第一个匹配项就停止
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Deque;
import java.util.ArrayDeque;

public class OrganizationSearcher {

    private List<Department> rootDepartments; // 假设这是整个组织结构的根部门列表

    public OrganizationSearcher(List<Department> rootDepartments) {
        this.rootDepartments = rootDepartments;
    }

    /**
     * 公开方法：通过递归方式查找所有指定类型的部门
     * @param type 要查找的部门类型
     * @return 匹配指定类型的所有部门列表
     */
    public List<Department> findDepartmentByTypeRecursive(String type) {
        ArrayList<Department> result = new ArrayList<>();
        // 从根部门列表开始递归搜索
        findDepartmentByTypeRecursiveImpl(type, rootDepartments, result);
        return result;
    }

    /**
     * 私有辅助方法：执行递归深度优先搜索
     * @param type 要查找的部门类型
     * @param departments 当前层级的部门列表
     * @param result 收集匹配部门的结果列表
     */
    private void findDepartmentByTypeRecursiveImpl(String type, List<Department> departments, List<Department> result) {
        if (departments == null || departments.isEmpty()) {
            return; // 基本情况：当前部门列表为空，停止递归
        }

        for (Department current : departments) {
            // 1. 检查当前部门是否匹配
            if (type.equals(current.getType())) {
                result.add(current);
            }

            // 2. 如果当前部门是公司（即有子部门），则递归遍历其子部门
            if (current instanceof Company) {
                // 向下转型为Company，获取其子部门列表
                findDepartmentByTypeRecursiveImpl(type, ((Company) current).getDepartments(), result);
            }
        }
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Deque;
import java.util.ArrayDeque;

public class OrganizationSearcher {
    // ... (同上，包含rootDepartments和构造函数)

    /**
     * 公开方法：通过迭代方式（使用栈）查找所有指定类型的部门
     * @param type 要查找的部门类型
     * @return 匹配指定类型的所有部门列表
     */
    public List<Department> findDepartmentByTypeIterative(String type) {
        ArrayList<Department> result = new ArrayList<>();
        // 使用Deque作为栈，ArrayDeque是推荐的实现
        Deque<Department> stack = new ArrayDeque<>();

        // 将所有根部门压入栈中，作为遍历的起点
        if (rootDepartments != null) {
            for (Department dept : rootDepartments) {
                stack.push(dept); // 使用push将元素压入栈顶
            }
        }

        // 当栈不为空时，持续进行遍历
        while (!stack.isEmpty()) {
            Department current = stack.pop(); // 弹出栈顶元素进行处理

            // 1. 检查当前部门是否匹配
            if (type.equals(current.getType())) {
                result.add(current);
            }

            // 2. 如果当前部门是公司，则将其子部门压入栈中
            // 注意：为了保持DFS的顺序（通常是先访问左子树再右子树），
            // 如果希望子部门按特定顺序处理，压栈时需要注意顺序。
            // 这里我们简单地将所有子部门压入，实际遍历顺序可能与递归略有不同，但最终会访问所有节点。
            if (current instanceof Company) {
                List<Department> children = ((Company) current).getDepartments();
                if (children != null) {
                    // 逆序压入子部门，以确保在后续pop时，能够以预期的顺序（例如，与原列表顺序一致）处理
                    // 或者，如果顺序不重要，直接addAll即可
                    for (int i = children.size() - 1; i >= 0; i--) {
                        stack.push(children.get(i));
                    }
                }
            }
        }
        return result;
    }
}