algorithm - 查找 k 阶斐波那契树中两个节点之间的路径

Question

有一棵二叉斐波那契树，其左子树的阶数为(n-2)，右子树的阶数为(n-1)。我们在构造树的时候，会按照预序的方式对节点进行标记，根从0开始，这样每个节点都有一个唯一的值。

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

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

我认为通过构造第二棵树，然后找到两个节点的最低公共(public)祖先，计算此输出非常简单。与以下问题的解决方案基本相同: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_tree(order):
    fib_trees = [Leaf(), Leaf()]
    while len(fib_trees) <= order:
        fib_trees.append(Branch(fib_trees[-2], fib_trees[-1]))
    return fib_trees[order]


def left_divide(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_path(order, source, dest):
    tree = fib_tree(order)
    return left_divide(tree.path(source), tree.path(dest))


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