java - 一个数学函数可以让我们得到特定类型 k-ary 的叶子数？

Question

我想找出一个函数 f(x) 来计算 k 叉树中的叶子数。例如，假设我们创建了一棵树，它以根 4 开始，有 3 个 child ，每个 child 分别为 -1、-2、-3。我们的叶子只会是 0 值，而不是空值。在过去的一天里，我一直在尝试找出一个函数，但似乎我所做的一切都没有朝着正确的方向发展。

例如:

              4
         /    |     \
        3     2      1
     /  |\   /|     /  
    2   1 0 1 0    0  
   /|  /   /
  1 0 0   0
 /
0

7 片叶子。

任何帮助将不胜感激!谢谢!

为了澄清，我需要一个数学方程式，它可以得出与我递归遍历树时代码得出的答案相同的答案。

更多例子:{4,7}{5,13}{6,24}{7,44}{8,81}{9,149}{10,274}{11,504}{12,927}{13,1705}{14,3136}{15, 5768}{16,10609}{17,19513}{18,35890}{19,66012}{20,121415}

 public int numleaves(TreeNode node) {
    if (node == null)
        return 0; 
    else if (node.getLeft() == null && node.getMiddle() == null && node.getRight() == null)
        return 1; 
    else
        return numleaves(node.getLeft()) + numleaves(node.getMiddle()) + numleaves(node.getRight());
}

Answer 1

我无法回答你的问题，但它有一个 solution .我只能概述子代数 k 等于 2 的情况。 k=3 的情况导致具有两个复数和一个实数解的三次多项式，我这里缺少以非数值方式推导它们的工具。

但让我们看一下 k=2 的情况。有趣的是，除了边界条件不同之外，这个问题与斐波那契数列非常相关。

写下递归公式很容易:

a(n) = a(n-1) + a(n-2)

具有边界条件 a(1)=1 和 a(0)=1。其特征多项式为

x^2 = x + 1

使用解决方案 x1 = 1/2 + sqrt(5)/2 和 x2 = 1/2 - sqrt(5)/2。这意味着

a(n) = u*x1^n + v*x2^n

对于某些 u 和 v 是我们正在寻找的序列的显式公式。放入边界条件我们得到

u = (sqrt(5)+1)/(2*sqrt(5))
v = (sqrt(5)-1)/(2*sqrt(5))

即

a(n) = (sqrt(5)+1)/(2*sqrt(5))*(1/2 + sqrt(5)/2)^n + (sqrt(5)-1)/(2*sqrt(5))*(1/2 - sqrt(5)/2)^n

k=2。