如何在Java中将父子关系表转为树形结构？非递归方案探讨

递归实现树形结构虽然代码简洁，但数据量较大时容易触发栈溢出，且时间复杂度的常数项较高。更优的方案是借助哈希表（Map）实现一次遍历构建，时间复杂度为O(n)，空间复杂度为O(n)，效率和稳定性都更出色。

实现思路 #

1. 先将所有节点存入哈希表，以id为键、Person对象为值，实现O(1)时间复杂度的父节点查找
2. 遍历所有节点，根据parentId从哈希表中取出父节点，将当前节点添加到父节点的childs列表中
3. 最后筛选出parentId为0的根节点，组成最终的树形结构根列表

完整Java代码 #

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 定义Person类
class Person {
    private String name;
    private Integer id;
    private Integer parentId;
    private List<Person> childs = new ArrayList<>();

    // 构造方法
    public Person(String name, Integer id, Integer parentId) {
        this.name = name;
        this.id = id;
        this.parentId = parentId;
    }

    // Getter和Setter（按需使用）
    public String getName() {
        return name;
    }

    public Integer getId() {
        return id;
    }

    public Integer getParentId() {
        return parentId;
    }

    public List<Person> getChilds() {
        return childs;
    }
}

public class TreeBuilder {
    public static void main(String[] args) {
        // 模拟原始数据源
        List<Person> rawData = new ArrayList<>();
        rawData.add(new Person("A", 1, 0));
        rawData.add(new Person("B1", 2, 1));
        rawData.add(new Person("B2", 3, 1));
        rawData.add(new Person("C1", 4, 2));
        rawData.add(new Person("C2", 5, 3));
        rawData.add(new Person("D1", 6, 5));

        List<Person> parentList = buildTree(rawData);
        // 可添加打印、验证逻辑
    }

    public static List<Person> buildTree(List<Person> rawData) {
        Map<Integer, Person> nodeMap = new HashMap<>();
        List<Person> rootNodes = new ArrayList<>();

        // 第一步：将所有节点存入Map
        for (Person person : rawData) {
            nodeMap.put(person.getId(), person);
        }

        // 第二步：遍历节点，挂载子节点到对应父节点
        for (Person person : rawData) {
            Integer parentId = person.getParentId();
            if (parentId == 0) {
                rootNodes.add(person);
            } else {
                Person parent = nodeMap.get(parentId);
                if (parent != null) {
                    parent.getChilds().add(person);
                }
            }
        }

        return rootNodes;
    }
}

方案优势 #

• 时间效率高：仅需两次线性遍历，无递归调用的额外开销
• 稳定性强：非递归实现，不受JVM栈深度限制，支持大规模数据场景
• 易维护扩展：逻辑清晰，后续新增节点属性或调整树形规则时更易修改

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