非二叉树中特定级别的子节点数

Question

我正在尝试创建一个方法

 public int getNumberOfChildNodes(int level)

这将返回特定级别的许多子节点。下图中的说明：Level 1 should return 2 (B and C) and level 2 should return 5 (D, E, F, G, H)

我已经创建了一个代码，它返回树的高度并返回所有子节点的数量，但是我无法知道如何仅在特定级别找出childNodes的数量。谢谢！

import java.util.*;

public class Tree {

private String name;
private List<Tree> childNodes = new ArrayList<Tree>();

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

public void addChildNode(Tree childNode) {
    childNodes.add(childNode);
}


public int getNumberOfChildNodes() {
    int result = 0;
    for (Tree childNode : childNodes){
        result += childNode.getNumberOfChildNodes();
   }
    return result + childNodes.size();
}

/*

public int getNumberOfChildNodes(int level) {
    int result = 0;        
    for (Tree childNode : childNodes) {
        result += childNode.getNumberOfChildNodes();
 }
    return result + childNodes.size();    }
*/

}

Answer 1

试试这个递归函数：

public int getNumberOfChildNodes(int level) {
    if(level == 0)
        return childNodes.size();

    int numOfChildren = 0;
    for (Tree childNode : childNodes) {
        numOfChildren += childNode.getNumberOfChildNodes(level-1);
    }

    return numOfChildren ;
}

想法是扫描每个级别。对于每次递归调用，我们将级别降低1.因此，当level==0表示我们处于我们想要的级别的节点时，我们将返回此节点的size()。

编辑

在这个解决方案中，我假设每个节点的级别是与根的距离（即根级别为0级，其子级别为1级，依此类推）。