Java 遞歸遍歷樹形結構實現折疊菜單

場景與核心思路

將扁平化的菜單/部門/分類數據（含 id、parentId）轉換為樹形 JSON，用於前端遞歸渲染（如 Ant Design Tree、Vue Tree、zTree）。核心算法：遞歸查找子節點，時間複雜度 O(n²)；優化版使用 Map 索引 + 單次遍歷 達到 O(n)。

基礎遞歸版（適合數據量較小）

import net.sf.json.JSONArray;
import net.sf.json.JSONObject;

public class TreeMenuUtil {
    /**
     * 遞歸構建子樹
     * @param menuList 扁平菜單數據
     * @param parentId 父節點 ID
     * @return 子節點 JSONArray
     */
    public JSONArray buildTree(JSONArray menuList, int parentId) {
        JSONArray children = new JSONArray();
        for (Object obj : menuList) {
            JSONObject node = JSONObject.fromObject(obj);
            int id = node.getInt("id");
            int pid = node.getInt("parentId");
            if (pid == parentId) {
                JSONArray subChildren = buildTree(menuList, id);
                node.put("childNode", subChildren);
                children.add(node);
            }
        }
        return children;
    }

    // 測試主方法
    public static void main(String[] args) {
        JSONArray list = new JSONArray();
        // 模擬數據：id, parentId, level
        addMenu(list, 1, 0, 0);
        addMenu(list, 2, 0, 0);
        addMenu(list, 3, 2, 1);
        addMenu(list, 4, 2, 1);
        addMenu(list, 5, 4, 2);
        addMenu(list, 6, 1, 1);

        TreeMenuUtil util = new TreeMenuUtil();
        System.out.println(util.buildTree(list, 0));
    }

    private static void addMenu(JSONArray list, int id, int pid, int level) {
        JSONObject m = new JSONObject();
        m.put("id", id);
        m.put("parentId", pid);
        m.put("level", level);
        list.add(m);
    }
}

高性能 Map 索引版（推薦生產環境）

import java.util.*;

public class TreeBuilder {
    public static List<TreeNode> build(List<TreeNode> flatList) {
        // 1. 建立 id -> Node 映射
        Map<Integer, TreeNode> nodeMap = new HashMap<>();
        for (TreeNode node : flatList) {
            nodeMap.put(node.getId(), node);
        }

        // 2. 根節點收集器
        List<TreeNode> roots = new ArrayList<>();

        // 3. 單次遍歷掛載子節點
        for (TreeNode node : flatList) {
            Integer pid = node.getParentId();
            if (pid == null || pid == 0) {
                roots.add(node); // 根節點
            } else {
                TreeNode parent = nodeMap.get(pid);
                if (parent != null) {
                    parent.getChildren().add(node);
                } else {
                    // 父節點缺失，視為根或拋異常
                    roots.add(node);
                }
            }
        }
        return roots;
    }

    // 實體類
    public static class TreeNode {
        private Integer id;
        private Integer parentId;
        private String name;
        private List<TreeNode> children = new ArrayList<>();

        // getter/setter 省略
        public Integer getId() { return id; }
        public void setId(Integer id) { this.id = id; }
        public Integer getParentId() { return parentId; }
        public void setParentId(Integer parentId) { this.parentId = parentId; }
        public String getName() { return name; }
        public void setName(String name) { this.name = name; }
        public List<TreeNode> getChildren() { return children; }
        public void setChildren(List<TreeNode> children) { this.children = children; }
    }
}

數據庫層面優化

• 使用 WITH RECURSIVE (PostgreSQL、MySQL 8.0+) 單條 SQL 查詢全樹。
• 或採用 閉包表 / 路徑枚舉 存儲祖先路徑，查詢子樹變為 LIKE 'path/%'，極大提升讀性能。

前端渲染提示

• 後端返回 children 字段為空數組 [] 而非 null，避免前端報錯。
• 大數據量建議啟用虛擬滾動或懶加載（點擊展開再請求子節點）。
• 配合 expandedKeys、selectedKeys 實現狀態受控。

總結

遞歸版代碼簡潔，適合數據量＜1000 且層級不深的場景；Map 索引版線性時間、無棧溢出風險，適合生產環境。根據業務量級選擇，並考慮數據庫層面優化。