求树中节点最大子节点数：Java代码层级读取错误问题求助

我来帮你搞定这个问题！你的当前代码只检查了当前节点的直接子节点的子节点数量，没有递归遍历整个树的所有节点，所以会漏掉更深层级里拥有更多子节点的节点。比如如果某个孙子节点有8个子节点，但你的直接子节点最多只有3个，你的代码会错误地返回3而不是8。

问题代码分析 #

原方法的逻辑局限在两层节点：

public int returnMaxChildren() {
    int count = children.size();
    for (Person child : children)
        if (child.children.size() > count)
            count = child.children.size();
    return count;
}

它只对比了当前节点的子节点数，和每个直接子节点的子节点数，完全没深入到子节点的子树里去查找最大值。

修复后的代码 #

我们需要用递归遍历树的每一个节点，记录遍历过程中遇到的最大子节点数：

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

public class Person {
    private String name;
    private List<Person> children = new ArrayList<Person>();

    public Person(String name) {
        this.name = name;
    }

    public void addChild(Person child) {
        children.add(child);
    }

    public int returnMaxChildren() {
        // 先记录当前节点的子节点数作为初始最大值
        int maxCount = children.size();
        
        // 遍历每个子节点，递归查找该子树中的最大子节点数
        for (Person child : children) {
            int childTreeMax = child.returnMaxChildren();
            // 如果子树的最大值更大，更新当前最大值
            if (childTreeMax > maxCount) {
                maxCount = childTreeMax;
            }
        }
        
        return maxCount;
    }

    // 测试用的main方法，验证逻辑正确性
    public static void main(String[] args) {
        // 构建测试树结构
        Person root = new Person("Root");
        Person child1 = new Person("Child1");
        Person child2 = new Person("Child2");
        
        // 给Child2添加5个子节点
        for (int i = 0; i < 5; i++) {
            child2.addChild(new Person("Grandchild" + i));
        }
        
        // 给某个孙子节点添加7个子节点（更深层级）
        Person deepChild = child2.children.get(3);
        for (int i = 0; i < 7; i++) {
            deepChild.addChild(new Person("GreatGrandchild" + i));
        }
        
        root.addChild(child1);
        root.addChild(child2);
        
        // 预期返回7，而非5
        System.out.println(root.returnMaxChildren()); // 输出7
    }
}

代码逻辑说明 #

1. 初始时，把当前节点的子节点数设为maxCount作为基准值
2. 对每个子节点，递归调用returnMaxChildren()，获取该子树中所有节点的最大子节点数
3. 把每个子树的最大值和当前maxCount对比，保留更大的那个数值
4. 最终返回的就是整个树中任意节点拥有的最大子节点数

这样不管节点在树的哪一层，都会被遍历到，不会错过任何可能的最大值。

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