问题:我有一个二叉树，所有叶子都编号(从左到右，从 0 开始)并且它们之间不存在连接。
我想要一种算法，给定两个索引(2 个不同的叶子)，从较大的叶子(索引较高的叶子)开始访问树并到达较低的叶子。
树的内部节点不包含任何有用的信息。
我应该只根据叶子索引来选择路径。路径从一片叶子开始到一片叶子结束，当然如果我知道它的索引(通过指针数组)我就可以访问一片叶子
树是静态的，不允许插入或删除节点。
我已经开发了一种算法来做到这一点，但它真的很糟糕......有什么想法吗？
最佳答案
一个选择是找到两个节点的最不公共(public)祖先，以及您应该从每个节点获取的节点序列以到达该祖先。这是算法的草图:
从每个节点开始，返回到该节点的父节点，直到到达根节点。统计从每个节点到根节点的路径上的节点数。令第一个节点的高度为h1，第二个节点的高度为h2。
设 h = min(h1, h2)。这是两个节点中较高节点的高度。
从每个节点开始，一直跟随节点的父指针，直到两个节点的高度都为h。记录您在此步骤中遵循的节点。此时，两个节点的高度相同。
在找到公共(public)节点之前，继续从每个节点向上行进到其父节点。最终你会击中他们的共同祖先。此时，沿着从第一个节点到这个祖先的路径，然后沿着从祖先的路径向下到第二个节点。
在最坏的情况下，这需要 O(h) 的时间和 O(h) 的空间，其中 h 是树的高度。对于一棵平衡二叉树来说就是这个O(lg n)的时间和空间，已经很不错了。
如果您对该算法的更硬核版本感兴趣，请考虑查看 Tarjan's Least Common Ancestors具有线性预处理时间的算法可以比这更快地找到最小公共(public)祖先。
希望这对您有所帮助!
关于algorithm - 二叉树访问: get from one leaf to another leaf，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5115798/