在树中查找子节点的最大数量

Question

我正在尝试创建一个方法，它将返回任何节点拥有的最大数量的子节点（子节点）。但是，我的代码错误地读取了深层次。

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 count = children.size();
    for (Person child : children)
        if (child.children.size() > count)
            count = child.children.size();
    return count;
}

Answer 1

您的代码占用当前节点的子节点数，然后将其与孙子节点数（当前子节点的子节点）进行比较。但就是这样。

如果你想获得任何后代节点的最大子节点，你可能想让孩子通过递归调用returnMaxChildren来计算他们的最大值。

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

Answer 2

首先，您需要一种方法来计算所有孩子：

public int countChildren() {
    int retVal = children.size();
    for (Person child : children) {
        retVal += child.countChildren();
    }
    return retVal;
}

有了它，您可以在对象中查找节点最多的子节点：

public int returnMaxChildren() {
    int retVal = 0;
    for (Person child : children) {
        if (child.countChildren() > retVal) {
            retVal = child.countChildren();
        }
    }
    return retVal;
}