我有多个二叉树存储为数组。每个槽中要么是 nil（或 null；选择您的语言），要么是存储两个数字的固定元组：两个“子项”的索引。任何节点都不会只有一个子节点——要么没有，要么有两个。

将每个槽视为一个二进制节点，仅存储指向其子节点的指针，并且没有固有值。

以这个二叉树系统为例：

    0       1
   / \     / \
  2   3   4   5
 / \         / \
6   7       8   9
   / \
 10   11
  

关联的数组将是：

   0       1       2      3     4      5      6      7        8     9     10    11
[ [2,3] , [4,5] , [6,7] , nil , nil , [8,9] , nil , [10,11] , nil , nil , nil , nil ]

我已经编写了简单的函数来查找节点的直接父节点（只需从前面搜索直到存在包含子节点的节点）

此外，假设在相关时间，所有树的深度都在几层到几千层之间。

我想找一个函数

P(m,n)

找到 m 和 n 的最低共同祖先——更正式地说，LCA 被定义为“最低”或最深的节点，其中 m 和 n 作为后代（子代或子代的子代等）。如果没有，则 nil 将是有效返回。

给定我们给定的树的一些示例：

P( 6,11)   # => 2
P( 3,10)   # => 0
P( 8, 6)   # => nil
P( 2,11)   # => 2

我能找到的主要方法是使用欧拉迹，它将给定的树（添加节点 A 作为 0 和 1 的不可见父节点，“值”为 -1）转换为：

A-0-2-6-2-7-10-7-11-7-2-0-3-0-A-1-4-1-5-8-5-9-5-1-A

由此，只需找到给定的 m 和 n 之间编号最小的节点即可；例如，要查找 P(6,11)，请在迹线上查找 6 和 11。它们之间最小的数字是 2，这就是你的答案。如果 A (-1) 位于它们之间，则返回 nil。

 -- Calculating P(6,11) --

A-0-2-6-2-7-10-7-11-7-2-0-3-0-A-1-4-1-5-8-5-9-5-1-A
      ^ ^        ^
      | |        |
      m lowest   n

不幸的是，我确实相信找到一棵树的欧拉迹可以几千深度的层次对机器来说有点繁重……而且因为我的树在整个编程过程中不断变化，每次我想找到 LCA 时，我都必须重新计算欧拉迹并保存它每次都在记忆中。

考虑到我正在使用的框架，是否有更有效的内存方法？一个可能向上迭代的？我能想到的一种方法是“计算”两个节点的生成/深度，并爬升最低节点直到它与最高节点的深度匹配，并增加两者直到找到类似的节点。

但这需要从 3025 级上升到 0 级，twice，计算一代，并首先使用效率极低的爬升算法，然后重新爬回来。

还有其他更好的方法吗？

澄清

在这个系统的构建方式中，每个孩子的数字都会比他们的父母大.

这确实not保证如果 n 在第 X 代中，则第 (X-1) 代中没有大于 n 的节点。例如：

        0
       / \
      /   \
     /     \
    1       2        6
   / \     / \      / \
  2   3   9  10    7   8
     / \              / \
    4   5            11 12
  

是一个有效的树系统。

此外，树的构建方式的一个缺陷是同一父代的两个直接子代将始终连续编号。

节点的顺序是否像您的示例中那样，子级的 id 大于父级？如果是这样，您也许可以执行类似于合并排序的操作来找到它们。对于您的示例，6 和 11 的父树是：

6  -> 2 -> 0
11 -> 7 -> 2 -> 0

所以也许算法是：

left = left_start
right = right_start

while left > 0 and right > 0
    if left = right
        return left
    else if left > right
        left = parent(left)
    else
        right = parent(right)

它将运行为：

left    right
----    -----
 6        11    (right -> 7)
 6        7     (right -> 2)
 6        2     (left -> 2)
 2        2     (return 2)

它是否正确？