如何计算树中给定算法的节点数量？

Question

我有一个问题，我需要帮助。我给出了：

int sum(int[] array, int first, int last) 
{ 
if (first == last) 
return array[first]; 
int mid = (first + last)/2; 
return sum(array, first, mid) + sum(array, mid + 1, last); 
} 

问题：确定一个计算递归树中节点数的公式。

所以，我得到的递归等式： T（N）= 2T（N/2）+ DN

而且例如用于长度为8的中递归树的阵列，节点的数目将是15 ，这表明树中节点的数量是2n-1，其中n是数组的大小。

我想知道我的想法是否正确，并且2n-1公式能否适用于任何情况？另外，有没有一种通用的方法来计算递归树中给定递归算法的节点数？

谢谢你的帮助！

Answer 1

 2 
    /\ 
    1 1 // 2(n) - 1 = 2(2) - 1 = 3 seems to match! 

     3 
    /\ 
    2 1 
/\ 
    1 1  // 2(n) - 1 = 2(3) - 1 = 5 which seems to match 

计算一些其他的例子，公式2（n） - 1似乎是正确的。