非二叉树节点搜索：根到节点路径与后代查询实现咨询

嘿，我来帮你搞定这两个树节点搜索的需求，结合你给出的TreeNodeDTO类，我整理了清晰可复用的实现方案，直接就能用👇

实现思路 #

• 采用**深度优先搜索(DFS)**的方式遍历树，这种方式天然适合回溯路径，能方便追踪从根到当前节点的完整路径
• 维护一个临时路径列表，每进入一个节点就加入路径，遍历完所有子节点后移除当前节点（回溯操作），保证路径的正确性
• 当找到匹配节点时，必须保存路径的副本到结果集，避免后续回溯修改已保存的路径

完整代码实现 #

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

public class TreeNodeDTO {
    private String id;
    private String title;
    private List<TreeNodeDTO> children;

    // 建议添加构造函数，方便树节点创建
    public TreeNodeDTO(String id, String title) {
        this.id = id;
        this.title = title;
        this.children = new ArrayList<>();
    }

    // Getter和Setter方法（此处省略，根据IDE自动生成即可）
    public String getId() { return id; }
    public void setId(String id) { this.id = id; }
    public String getTitle() { return title; }
    public void setTitle(String title) { this.title = title; }
    public List<TreeNodeDTO> getChildren() { return children; }
    public void setChildren(List<TreeNodeDTO> children) { this.children = children; }

    // 对外暴露的方法：搜索目标节点，返回所有根到目标的路径
    public List<List<TreeNodeDTO>> findPathsToTargets(String targetTitle) {
        List<List<TreeNodeDTO>> resultPaths = new ArrayList<>();
        List<TreeNodeDTO> currentPath = new ArrayList<>();
        dfsPathTraversal(this, targetTitle, currentPath, resultPaths);
        return resultPaths;
    }

    // 私有DFS递归方法，处理路径追踪逻辑
    private void dfsPathTraversal(TreeNodeDTO currentNode, String targetTitle, 
                                 List<TreeNodeDTO> currentPath, List<List<TreeNodeDTO>> resultPaths) {
        if (currentNode == null) {
            return;
        }

        // 将当前节点加入路径
        currentPath.add(currentNode);

        // 匹配到目标节点，保存路径副本
        if (currentNode.getTitle().equals(targetTitle)) {
            resultPaths.add(new ArrayList<>(currentPath));
            // 注意：这里不要直接return，因为可能存在多个同名节点需要继续搜索
        }

        // 递归遍历所有子节点
        for (TreeNodeDTO child : currentNode.getChildren()) {
            dfsPathTraversal(child, targetTitle, currentPath, resultPaths);
        }

        // 回溯：移除当前节点，回到父节点的路径状态
        currentPath.remove(currentPath.size() - 1);
    }
}

关键注意点 #

• 如果需要按id搜索而非title，只需要把currentNode.getTitle().equals(targetTitle)替换为currentNode.getId().equals(targetId)即可
• 必须保存路径的副本，如果直接添加currentPath到结果集，后续回溯操作会修改这个列表，导致最终结果全部变成空或错误路径

实现思路 #

• 拆分逻辑为两步：先找到所有匹配的目标节点，再逐个收集每个匹配节点的所有后代（子节点、孙节点等）
• 同样用DFS遍历树，保证不遗漏任何层级的节点
• 你原代码里的!this.title.equals("Root")判断可以按需保留，用于排除根节点的匹配

完整代码实现（基于你的原有代码完善） #

// 在TreeNodeDTO类中添加以下方法
// 对外暴露的方法：搜索匹配节点，返回所有匹配节点的后代集合
public List<TreeNodeDTO> searchDescendants(String searchTitle) {
    List<TreeNodeDTO> allDescendants = new ArrayList<>();
    // 第一步：找到所有匹配标题的节点
    List<TreeNodeDTO> matchedNodes = findAllMatchedNodes(this, searchTitle);
    
    // 第二步：为每个匹配节点收集其所有后代
    for (TreeNodeDTO matchedNode : matchedNodes) {
        allDescendants.addAll(getAllDescendantsOfNode(matchedNode));
    }
    return allDescendants;
}

// 辅助方法：遍历树，找到所有匹配标题的节点
private List<TreeNodeDTO> findAllMatchedNodes(TreeNodeDTO currentNode, String searchTitle) {
    List<TreeNodeDTO> matchedList = new ArrayList<>();
    if (currentNode == null) {
        return matchedList;
    }

    // 如果需要排除根节点，添加判断：!currentNode.getTitle().equals("Root")
    if (currentNode.getTitle().equals(searchTitle)) {
        matchedList.add(currentNode);
    }

    // 递归遍历子节点
    for (TreeNodeDTO child : currentNode.getChildren()) {
        matchedList.addAll(findAllMatchedNodes(child, searchTitle));
    }
    return matchedList;
}

// 辅助方法：获取单个节点的所有后代（不含节点自身，如需包含可在开头添加matchedList.add(currentNode)）
private List<TreeNodeDTO> getAllDescendantsOfNode(TreeNodeDTO currentNode) {
    List<TreeNodeDTO> descendants = new ArrayList<>();
    if (currentNode == null || currentNode.getChildren() == null || currentNode.getChildren().isEmpty()) {
        return descendants;
    }

    // 添加直接子节点
    descendants.addAll(currentNode.getChildren());
    // 递归遍历每个子节点的后代
    for (TreeNodeDTO child : currentNode.getChildren()) {
        descendants.addAll(getAllDescendantsOfNode(child));
    }
    return descendants;
}

关键注意点 #

• 如果需要包含匹配节点自身到后代集合中，只需要在getAllDescendantsOfNode方法的开头添加descendants.add(currentNode);即可
• 拆分逻辑后代码更易维护，后续如果需要修改匹配规则或后代收集规则，只需修改对应辅助方法即可

public static void main(String[] args) {
    // 构建测试树结构
    TreeNodeDTO root = new TreeNodeDTO("1", "Root");
    TreeNodeDTO nodeA = new TreeNodeDTO("2", "A");
    TreeNodeDTO nodeB = new TreeNodeDTO("3", "B");
    TreeNodeDTO nodeA1 = new TreeNodeDTO("4", "A");
    TreeNodeDTO nodeB1 = new TreeNodeDTO("5", "B1");
    TreeNodeDTO nodeA11 = new TreeNodeDTO("6", "A11");
    
    root.getChildren().add(nodeA);
    root.getChildren().add(nodeB);
    nodeA.getChildren().add(nodeA1);
    nodeA1.getChildren().add(nodeA11);
    nodeB.getChildren().add(nodeB1);

    // 测试需求1：搜索标题为"A"的节点，获取根到它们的路径
    List<List<TreeNodeDTO>> paths = root.findPathsToTargets("A");
    System.out.println("=== 根到目标节点的路径 ===");
    for (List<TreeNodeDTO> path : paths) {
        path.forEach(n -> System.out.print(n.getTitle() + " -> "));
        System.out.println("END");
    }

    // 测试需求2：搜索标题为"A"的节点，获取它们的后代
    List<TreeNodeDTO> descendants = root.searchDescendants("A");
    System.out.println("\n=== 匹配节点的后代 ===");
    descendants.forEach(n -> System.out.println(n.getTitle()));
}

输出结果 #

=== 根到目标节点的路径 ===
Root -> A -> END
Root -> A -> A -> END

=== 匹配节点的后代 ===
A
A11

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