如何将任意多叉树转换为符合子节点数量约束的n叉树，保持祖先顺序不变

需求重述 #

给定任意结构的多叉树根节点，需实现转换方法满足以下规则：

• 转换后除最多1个例外节点外，其余所有节点要么恰好有N个子节点，要么没有子节点；例外节点的子节点数量允许在0~N之间。
• 若原树中节点A是节点B的祖先，转换后节点B不能成为节点A的祖先，二者可以是同级节点。

核心实现思路 #

1. 拓扑排序拉平节点：对原树做前序遍历，将所有节点按顺序收集到列表中，保证原树中所有祖先节点都出现在后代节点之前，从根源避免转换后后代变成祖先的问题。
2. BFS逐层分配子节点：基于拉平的节点列表，用广度优先遍历的顺序给每个节点分配最多N个子节点，直到所有节点分配完成。这种分配方式只会让最后一个分配到子节点的节点的子节点数小于N，完全符合规则要求。

完整实现代码 #

import java.util.*;

interface CompactTreeBuilder<T> {
    Node<T> compact(Node<T> root, int N);
}

class Node<T> {
    private final T data;
    private final List<Node<T>> children;

    public Node(T data, List<Node<T>> children) {
        this.data = data;
        this.children = children;
    }

    public T getData() {
        return data;
    }

    public List<Node<T>> getChildren() {
        return children;
    }
}

public class CompactTreeBuilderImpl<T> implements CompactTreeBuilder<T> {

    // 辅助可变节点类，用于构建中间结构，最后转成不可变Node
    private static class MutableNode<T> {
        T data;
        List<MutableNode<T>> children = new ArrayList<>();

        MutableNode(T data) {
            this.data = data;
        }

        Node<T> toImmutableNode() {
            List<Node<T>> immutableChildren = children.stream()
                    .map(MutableNode::toImmutableNode)
                    .toList();
            return new Node<>(data, immutableChildren);
        }
    }

    @Override
    public Node<T> compact(Node<T> root, int N) {
        // 边界校验
        if (root == null || N <= 0) {
            return root;
        }

        // 1. 前序遍历收集所有节点的data，保证祖先顺序在前
        List<T> dataList = new ArrayList<>();
        preOrderCollect(root, dataList);
        if (dataList.size() == 1) {
            return new Node<>(root.getData(), Collections.emptyList());
        }

        // 2. 初始化所有可变节点，第一个为根节点
        List<MutableNode<T>> allMutableNodes = new ArrayList<>();
        for (T data : dataList) {
            allMutableNodes.add(new MutableNode<>(data));
        }
        MutableNode<T> newRoot = allMutableNodes.get(0);
        // 除根节点外的所有节点都是待分配的子节点
        List<MutableNode<T>> remainingNodes = allMutableNodes.subList(1, allMutableNodes.size());

        // 3. BFS分配子节点
        Queue<MutableNode<T>> queue = new LinkedList<>();
        queue.offer(newRoot);
        int pos = 0;
        int totalRemaining = remainingNodes.size();
        while (pos < totalRemaining) {
            MutableNode<T> current = queue.poll();
            // 最多取N个节点作为当前节点的子节点
            int takeCount = Math.min(N, totalRemaining - pos);
            for (int i = 0; i < takeCount; i++) {
                MutableNode<T> child = remainingNodes.get(pos + i);
                current.children.add(child);
                queue.offer(child);
            }
            pos += takeCount;
        }

        // 4. 转成不可变Node返回
        return newRoot.toImmutableNode();
    }

    // 前序遍历收集节点data
    private <T> void preOrderCollect(Node<T> node, List<T> dataList) {
        dataList.add(node.getData());
        for (Node<T> child : node.getChildren()) {
            preOrderCollect(child, dataList);
        }
    }
}

方案验证 #

完全匹配题干给出的所有示例：

• 当N=1时，每个节点只分配1个子节点，最终形成单链结构，和示例一致。
• 当N>=总节点数-1时，根节点直接挂载所有其他节点，和示例一致。
• 当N=2时，除最后一个分配子节点的节点外，其余节点的子节点数都是0或2，符合规则要求。

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