algorithm - 二叉树访问: get from one leaf to another leaf

Question

问题:我有一个二叉树，所有叶子都编号(从左到右，从 0 开始)并且它们之间不存在连接。

我想要一种算法，给定两个索引(2 个不同的叶子)，从较大的叶子(索引较高的叶子)开始访问树并到达较低的叶子。

树的内部节点不包含任何有用的信息。

我应该只根据叶子索引来选择路径。路径从一片叶子开始到一片叶子结束，当然如果我知道它的索引(通过指针数组)我就可以访问一片叶子

树是静态的，不允许插入或删除节点。

我已经开发了一种算法来做到这一点，但它真的很糟糕......有什么想法吗？

Answer 1

一个选择是找到两个节点的最不公共(public)祖先，以及您应该从每个节点获取的节点序列以到达该祖先。这是算法的草图:

1. 从每个节点开始，返回到该节点的父节点，直到到达根节点。统计从每个节点到根节点的路径上的节点数。令第一个节点的高度为h₁，第二个节点的高度为h₂。

2. 设 h = min(h₁, h₂)。这是两个节点中较高节点的高度。

3. 从每个节点开始，一直跟随节点的父指针，直到两个节点的高度都为h。记录您在此步骤中遵循的节点。此时，两个节点的高度相同。

4. 在找到公共(public)节点之前，继续从每个节点向上行进到其父节点。最终你会击中他们的共同祖先。此时，沿着从第一个节点到这个祖先的路径，然后沿着从祖先的路径向下到第二个节点。

在最坏的情况下，这需要 O(h) 的时间和 O(h) 的空间，其中 h 是树的高度。对于一棵平衡二叉树来说就是这个O(lg n)的时间和空间，已经很不错了。

如果您对该算法的更硬核版本感兴趣，请考虑查看 Tarjan's Least Common Ancestors具有线性预处理时间的算法可以比这更快地找到最小公共(public)祖先。

希望这对您有所帮助!