k阶斐波那契树两节点路径求解：动态规划替代方案探讨

斐波那契树定义 #

• 二叉斐波那契树结构规则：n阶树的左子树为(n-2)阶，右子树为(n-1)阶
• 节点标记规则：采用先序遍历方式标记节点，根节点编号从0开始，每个节点拥有唯一编号

5阶斐波那契树示例 #

• 标记前：遵循左子树为3阶、右子树为4阶的结构规则
• 标记后：通过先序遍历完成节点编号，形成连续唯一的节点序列

路径表示规则 #

两节点间的移动路径由以下字符组成：

• U：向上移动到父节点
• L：向下移动到左子节点
• R：向下移动到右子节点
  例如从节点5到7，对应的路径为UUURL

常规解法说明 #

常规思路是先完整构建标记后的斐波那契树结构，找到两个节点的最近公共祖先，再分别生成源节点到祖先、祖先到目标节点的路径，拼接后得到最终结果——这一解法本质上和LeetCode题目《从二叉树一个节点到另一个节点的分步路径》一致。

问题诉求 #

现寻求一种基于动态规划的替代解法，期望借助斐波那契树的结构特性来实现路径求解，无需将其当作普通二叉树进行全遍历。输入包含三个参数：斐波那契树的阶数、源节点编号、目标节点编号。示例输入如下：

• 阶数：5
• 源节点：5
• 目标节点：7

内容的提问来源于stack exchange，提问作者jmtt