在第 k 阶斐波那契树中找到两个节点之间的路径

Question

有一棵二叉斐波那契树，左子树的阶数为(n-2)，右子树的阶数为(n-1)。当我们构建树时，我们以 root 从 0 开始，以预先排序的方式标记节点，这样每个节点都有一个唯一的值。

重新标记前后的五阶斐波那契树：

假设我们想要找到从一个节点到另一个节点所需的步骤。为了从 5 到 7，我们输出“UUURL”，其中 U 表示向上，L 表示左孩子，R 表示右孩子。

我认为通过构建第二棵树，然后找到两个节点的最低共同祖先，计算这个输出非常简单。它与以下问题的解决方案基本相同：https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/

还有其他使用动态规划的解决方案吗？我觉得应该有一种方法可以利用斐波那契属性而不是处理一棵普通树并进行完整遍历。

编辑：输入是斐波那契树的顺序，源数，目的数。对于给定的示例，输入为

订单：5
来源：5
目的地：7

Answer 1

下面的 Python 解决方案将问题分解为三个部分。

1. 具有将深度优先索引转换为路径的方法的树的数据类型（Leaf 和 Branch 类）。这是通过索引访问树的经典方法。

2. 使用上述数据类型构建请求订单的斐波那契树。由于共享，这是有效的。

3. 将两条向下路径转换为一条向上路径，然后是一条向下路径。

我以牺牲效率为代价进行了优化，但这里的想法给出了一个按时间 O(order) 运行的算法。

class Leaf:
    def __len__(self):
        return 1

    def path(self, dest):
        assert 0 <= dest < len(self)
        return ""


class Branch:
    def __init__(self, left, right):
        self._left = left
        self._right = right
        self._len = 1 + len(left) + len(right)

    def __len__(self):
        return self._len

    def path(self, dest):
        assert 0 <= dest < len(self)
        if dest < 1:
            return ""
        dest -= 1
        if dest < len(self._left):
            return "L" + self._left.path(dest)
        dest -= len(self._left)
        return "R" + self._right.path(dest)


def fib_down(order, dest):
    fib_trees = [Leaf(), Leaf()]
    while len(fib_trees) <= order:
        fib_trees.append(Branch(fib_trees[-2], fib_trees[-1]))
    return fib_trees[order].path(dest)


def up_and_down(source_path, dest_path):
    n = min(len(source_path), len(dest_path))
    i = min((j for j in range(n) if source_path[j] != dest_path[j]), default=n)
    return "U" * (len(source_path) - i) + dest_path[i:]


def fib_up_and_down(order, source, dest):
    return up_and_down(fib_down(order, source), fib_down(order, dest))


print(fib_up_and_down(5, 5, 7))
# UUURL