java - 如何使用递归计算树中 child 的数量

Question

我设计了一个递归算法来查找字符串中子项的数量。字符串实际上是一个数组，例如[1,0,1,0,1]。这个字符串有三个可能的子字符串，它们是 [0,0,1,0,1]、[1,0,0,0,1] 和 [1,0,1,0,0]。因此，创建子项的标准是仅减少字符串中的一个非零条目。由于 [1,0,1,0,1] 中有三个非零条目，所以三个可能的 child 。以这种方式继续下去，每个 child 现在可以有两个可能的 child ，依此类推。当字符串中只有一个非零条目时递归停止。

这是我的代码:

public class Recursion {

/**
 * @param args the command line arguments
 */
    public static void main(String[] args) {
        // TODO code application logic here
        int[] c={1,0,1,0,1};
        System.out.println(num(c)); 
    }

    private static int num(int[] v){
        if(numChildren(v)==1){ 
            return 1;
        }    
        else{
            int[][] ge=children(v);
            for(int[] e:ge){
            return 1+num(e);
            }
            System.out.print("this return should never execute");
            return 0;
        }
    }

    private static int numChildren(int[] val){
        int sum=0;
        for(int i=0;i<val.length;i++){
            if(val[i]!=0){
                sum+=1;
            }   
        }
        return sum;
    }

    private static int[][] children(int[] p){
        int pChildern=numChildren(p);
        int[] d=new int[pChildern];
        int[][] r=new int[pChildern][];
        int c=0;
        for(int j=0;j<p.length;j++){
            if(p[j]!=0){
                d[c]=j;
                c++;
            }    
        }

        for(int i=0;i<pChildern;i++){
            p[d[i]]--;
            r[i]=p.clone();
            p[d[i]]++;
        }
        return r;
    }
}

我的代码确实执行了但没有产生正确的结果。它应该打印 6 但它打印了 3。

任何人都可以告诉我这段代码有什么问题吗？

Answer 1

// Returns size of subtree including the root
int getNumChilds(Node node) {
    int count = 1;
    for (Node child : node.getChildren()) {
        count += getNumChilds(child);
    }        
    return count;
}