我有多个二叉树存储在一个数组中。每个位置要么是nil（或null，根据您的语言选择），要么是一个固定的元组，存储两个数字：两个“子节点”的索引。没有节点只有一个子节点——它可以是没有或者有两个。
将每个位置看作只存储指向其子节点的二进制节点，而没有固有值。
以这个二叉树系统为例：
很遗憾，我认为找到一个可能有数千层深度的树的欧拉迹会对机器造成一定负担...而且因为我的树在编程过程中不断改变，每次想要找到LCA时，我都必须重新计算欧拉迹并将其保存在内存中。
考虑到我使用的框架，是否有更节省内存的方法？ 也许可以向上迭代？ 我能想到的一种方法是“计算”两个节点的生成/深度，并爬升最低节点，直到它与最高深度相匹配，并逐步增加两个节点，直到它们找到相似之处。
但这将涉及从级别（例如3025）向上爬升两次以计算代数，并且首先使用非常低效的爬升算法，然后重新爬升。
还有其他更好的方法吗？
澄清：
按照此系统构建的方式，“每个子项的编号都大于其父项”。
这并不保证如果n在第X代，则没有在第（X-1）代中比n大的节点。例如：
0 / \ / \ / \ 1 2 6 / \ / \ / \ 2 3 9 10 7 8 / \ / \ 4 5 11 12
是一个有效的树系统。
此外，树的构建方式的一个特点是同一父项的两个直接子项将始终按顺序编号。
将每个位置看作只存储指向其子节点的二进制节点，而没有固有值。
以这个二叉树系统为例：
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）向上爬升两次以计算代数，并且首先使用非常低效的爬升算法，然后重新爬升。
还有其他更好的方法吗？
澄清：
按照此系统构建的方式，“每个子项的编号都大于其父项”。
这并不保证如果n在第X代，则没有在第（X-1）代中比n大的节点。例如：
0 / \ / \ / \ 1 2 6 / \ / \ / \ 2 3 9 10 7 8 / \ / \ 4 5 11 12
是一个有效的树系统。
此外，树的构建方式的一个特点是同一父项的两个直接子项将始终按顺序编号。