Java实现树形结构列表中查询指定节点的所有父节点集合

• 通过深度优先遍历（DFS）扫描整棵树，遍历过程中记录当前遍历路径的父节点集合
• 若当前遍历节点的子节点命中目标名称，直接返回「父节点路径 + 目标子节点」组成的集合
• 单分支遍历未命中时，回溯移除当前节点的路径记录，继续遍历其他分支，全树未命中返回空集合

原MyNode类为私有属性，需补充构造方法、Getter和Setter才能正常操作：

public class MyNode {
    private String name;
    private List<MyNode> nodeList;

    // 构造方法
    public MyNode(String name) {
        this.name = name;
    }

    // Getter & Setter
    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public List<MyNode> getNodeList() {
        return nodeList;
    }

    public void setNodeList(List<MyNode> nodeList) {
        this.nodeList = nodeList;
    }
}

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

public class NodeSearcher {
    public static List<MyNode> findNodePath(List<MyNode> root, String targetName) {
        List<MyNode> path = new ArrayList<>();
        // 遍历根节点层级
        for (MyNode rootNode : root) {
            // 优先判断根节点本身是否命中目标
            if (targetName.equals(rootNode.getName())) {
                path.add(rootNode);
                return path;
            }
            if (dfs(rootNode, targetName, path)) {
                return path;
            }
        }
        // 未找到返回空集合
        return new ArrayList<>();
    }

    private static boolean dfs(MyNode currentNode, String targetName, List<MyNode> path) {
        // 当前节点没有子节点，直接返回未找到
        if (currentNode.getNodeList() == null || currentNode.getNodeList().isEmpty()) {
            return false;
        }
        // 遍历当前节点的所有子节点
        for (MyNode child : currentNode.getNodeList()) {
            // 子节点命中目标
            if (targetName.equals(child.getName())) {
                path.add(currentNode);
                path.add(child);
                return true;
            }
            // 递归遍历子节点的下级
            if (dfs(child, targetName, path)) {
                // 子分支找到目标，把当前节点加到路径头部
                path.add(0, currentNode);
                return true;
            }
        }
        return false;
    }

    // 测试方法
    public static void main(String[] args) {
        // 初始化测试树结构
        List<MyNode> root = new ArrayList<>();
        MyNode a = new MyNode("a");
        List<MyNode> aList  = new ArrayList<>();
        aList.add(new MyNode("a1"));
        aList.add(new MyNode("a2"));
        a.setNodeList(aList);

        MyNode b = new MyNode("b");
        List<MyNode> bList  = new ArrayList<>();
        bList.add(new MyNode("b1"));
        bList.add(new MyNode("b2"));
        b.setNodeList(bList);

        root.add(a);
        root.add(b);

        // 测试查找b1
        List<MyNode> result = findNodePath(root, "b1");
        // 输出结果节点名验证
        for (MyNode node : result) {
            System.out.println(node.getName());
        }
    }
}

运行测试代码后，输出内容为：

b
b1

和需求要求的返回集合完全一致，支持多级树结构的路径查找，比如存在b11是b1的子节点时，查找b11会返回[b, b1, b11]。

内容的提问来源于stack exchange，提问作者门心叼龙