java - 在没有动态规划的情况下以线性时间获取树中每个节点的后代数量？

Question

我编写了一个递归函数，用于计算 n 叉树中每个节点的后代数量。计算的结果在传入的数组中。我正在寻找一个以线性时间运行且不使用动态编程的函数。理想情况下，结果将设置在每个节点中，而不需要单独的数据结构。如果可能的话，递归是首选。

void setNumberDescendants(Node root, int[] descCount) {                                        
    for(Node child:root.children){
       setNumberDescendants(child, descCount);
       descCount[root.key] += 1+descCount[child.key];
    }        
} 

class Node{
    int key;    
    List<Node> children;     
} 

Answer 1

您的解决方案可以满足您的要求。

它是线性的：您只访问每个节点一次，并为每个节点做恒定的工作量。

它不使用动态规划：动态规划需要一个问题来展示重叠子问题和最优子结构。这个问题不表现出重叠的子问题。对于集合节点，您的子问题包括以该节点为根的子树的答案。这些子树不重叠。

如果要在每个节点中设置结果，只需执行以下操作：

void setNumberDescendants(Node root) {                                        
    for(Node child:root.children){
       setNumberDescendants(child);
       root.descendants += 1+child.descendants;
    }        
} 

class Node{
    int key;   
    int descendants; 
    List<Node> children;     
}