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

Question

我正在尝试找出一个函数 f(x) 来计算 k 叉树中的叶子数量。例如，假设我们创建了一棵树，从根 4 开始，有 3 个子节点，每个子节点分别为 -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 。我只能概述 child 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。