在二叉图中到达根节点的方法有多少？

Question

在下面的图表结构中，我们可以通过多少种方式从底层到达顶层？他们对这个问题有什么递归定义吗？假设我们在一步之后不能在同一层中，我们总是朝着根节点或峰值移动。

  O
 O O
O O O

这里n=3 (底层节点数=graph+1的高度)。对于这个图，我们有4种从底层移动到峰值的方法。我们如何将其推广到任何“n”？另外，我们如何使用动态编程来做到这一点呢？

Answer 1

假设从给定的节点只能向上、向左或向右爬升，那么结果似乎是2^N，其中N是树的高度。

说明:从节点(i，j)开始的路径数为c(i，j)=c(i-1，j-1)+c(i-1，j)。这产生了pascal triangle，其中每个级别N的和为2^N。

Answer 2

另一种观点：

让我们称c( n )为从深度n的层通向顶部的路数，因此我们有c(0)=1。由于n-1层中的每个节点都可以通过两种不同的方式从n层(从左侧或从右侧)到达，因此我们有c(n) = 2*c(n-1)。将其与c(0)=1组合得到c(n)=2^n。