Java中将嵌套方法调用转为递归实现指定深度多叉树构建

我需要构建一棵指定深度的多叉树（深度可由用户输入或常量指定），每个节点包含7个子节点，子节点同样各含7个子节点，以此类推。目前我通过嵌套方法调用实现了不同深度的节点添加，但希望将其转换为递归实现。以下是我的实现代码及尝试的递归方法，请帮忙修正：

原有非递归实现代码 #

MyTreeNode root = new MyTreeNode(new int[6][7]);

addChildren(root);// depth1

addChildrenToChildren(root.getChildren());// depth2

for (int i = 0; i < 7; i++) {
    addChildrenToChildren(root.getChildren().get(i).getChildren()); // depth3

}

for (int i = 0; i < 7; i++) {
    for (int j = 0; j < 7; j++) {
        addChildrenToChildren(root.getChildren().get(i).getChildren().get(j).getChildren()); // depth4

    }
}

使用的辅助方法 #

private static void addChildrenToChildren(List<MyTreeNode> children) {
    for(MyTreeNode child : children){
        addChildren(child);
    }
}

private static void addChildren(MyTreeNode root) {
        root.addChildren(Arrays.asList(
                new MyTreeNode(new int[6][7]),
                new MyTreeNode(new int[6][7]),
                new MyTreeNode(new int[6][7]),
                new MyTreeNode(new int[6][7]),
                new MyTreeNode(new int[6][7]),
                new MyTreeNode(new int[6][7]),
                new MyTreeNode(new int[6][7])
        ));
    }

尝试的递归方法（存在问题） #

public static void depth(MyTreeNode root, int n){
    if (n == 1){
        addChildren(root);
    } else {
        for (int i = 0; i < 7; i++) {
            addChildrenToChildren(root.getChildren());
            depth(root.getChildren().get(i), n - 1);
        }
    }
}

MyTreeNode类实现 #

public class MyTreeNode{
    private int[][] grid;
    private List<MyTreeNode> children = new ArrayList<MyTreeNode>();
    private MyTreeNode parent = null;

    public MyTreeNode(int[][] grid) {
        this.grid = grid;
    }

    public void addChild(MyTreeNode child) {
        child.setParent(this);
        this.children.add(child);
    }

    public void addChild(int[][] grid) {
        MyTreeNode newChild = new MyTreeNode(grid);
        this.addChild(newChild);
    }

    public void addChildren(List<MyTreeNode> children) {
        for(MyTreeNode t : children) {
            t.setParent(this);
        }
        this.children.addAll(children);
    }

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

    public int[][] getGrid() {
        return grid;
    }

    public void setGrid(int[][] grid) {
        this.grid = grid;
    }

    private void setParent(MyTreeNode parent) {
        this.parent = parent;
    }

    public MyTreeNode getParent() {
        return parent;
    }
}

修正后的递归实现 #

你的递归逻辑存在两个核心问题：

1. 终止条件错误：n=1时不应再添加子节点（根节点本身是深度1，目标深度为n意味着树从根到最底层叶子共有n层）
2. 循环逻辑冗余：重复调用addChildrenToChildren会导致节点被多次添加，且遍历子节点的方式不符合递归的层级递进逻辑

修正后的递归方法如下：

public static void buildTree(MyTreeNode root, int targetDepth) {
    // 终止条件：当前节点所在层级已达目标深度，停止添加子节点
    if (targetDepth <= 1) {
        return;
    }
    // 给当前节点添加7个子节点
    addChildren(root);
    // 递归处理每个子节点，目标深度减1（子节点所在层级比当前节点深1层）
    for (MyTreeNode child : root.getChildren()) {
        buildTree(child, targetDepth - 1);
    }
}

使用示例 #

如果要构建深度为4的树，调用方式如下：

MyTreeNode root = new MyTreeNode(new int[6][7]);
buildTree(root, 4);

逻辑说明 #

• 根节点是深度1，当targetDepth=4时：
  1. 给根节点添加子节点（对应深度2）
  2. 对每个深度2的节点，添加子节点（对应深度3）并递归处理
  3. 对每个深度3的节点，添加子节点（对应深度4）并递归处理，此时targetDepth-1=1触发终止条件，停止递归

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