这是我提出的用于非递归查找二叉树中两个节点的最低共同祖先的算法。以下是基本策略:
- 使用字典/哈希表来存储树。每个键值对代表一个节点及其父节点。
- 从两个节点中的每一个开始,通过将表示每个节点的值的变量设置为其父节点的值,将遍历的值存储在一个哈希集中(两个节点中的每一个节点一个),从而向上遍历树。
- 当满足以下任一条件时,搜索完成: (a) 两个节点的值相等;或 (b) 当两条路径相互交叉时(即节点 1 的遍历值的哈希集包含节点 2 的当前值,反之亦然);或 (c) 传入的节点在树中不存在(在这种情况下,算法终止并返回 -1)。
我的理解是,我的算法的最坏情况时间和空间复杂度是 O(log(n)),因为我们永远不需要进行超过 2 * 高度遍历或在哈希集中存储超过 2 * 高度值(并且因为哈希集和树字典的查找时间为 O(1))。
以下是我的代码(C#)。请告知我的分析是否正确,或者是否有更有效(非递归)的方法来执行此操作:
int LowestCommonAncestor(int value1, int value2, Dictionary<int, int> tree)
{
var value1Visited = new HashSet<int>();
var value2Visited = new HashSet<int>();
while (true)
{
if (value1 == value2) return value1;
if (value1Visited.Contains(value2)) return value2;
if (value2Visited.Contains(value1)) return value1;
int nextValue1;
int nextValue2;
if (tree.TryGetValue(value1, out nextValue1))
{
//Walk node 1 up the tree:
value1 = nextValue1;
value1Visited.Add(value1);
}
else
{
//Node doesn't exist in tree:
return -1;
}
if (tree.TryGetValue(value2, out nextValue2))
{
//Walk node 2 up the tree:
value2 = nextValue2;
value2Visited.Add(value2);
}
else
{
//Node doesn't exist in tree:
return -1;
}
}
}