这里用Java实现的二进制树中的LCA的时间复杂度是多少

Question

我有这个代码来查找binary tree中两个nodes的least common Ancestor。我认为时间复杂度是O(log n)。但需要专家的意见。这段代码在我的输入上运行得相当好，但我不确定我是否已经对它进行了详尽的测试。

这是代码

//LCA of Binary tree
public static Node LCABT(Node root, int v1, int v2){
if (root==null)
return null;
if (root.data==v1 || root.data==v2){
return root;
}
Node left = LCABT(root.left,v1,v2);
Node right = LCABT(root.right,v1,v2);
if(left!=null && right!=null)
return root;
else if (left!=null)
return left;
else  return right;
}

Answer 1

代码的时间复杂度是O(n)，因为您正在遍历整个树，即访问它的所有节点。但是，如果您没有BST，而只有一个二叉树，那么这是在父节点上没有指针的情况下可以实现的最佳效果(在这种情况下，构建从两个节点到根节点的路径，并返回两个路径中的节点)。如果您有BST，那么您可以定位这两个节点并在O(h)中找到最不常见的祖先，其中h是树的高度，如果树是平衡的，则为O(log n)。

最后一句话——如果你正在为比赛或面试做准备，一定要处理好角落里的案子。您的代码不处理其中一个节点不包含在树中的情况。

Answer 2

我很确定这会在O (n)中运行，因为你正在通过整个图(即，在每个节点上，你都在左右两个方向上)。

我建议阅读Tarjan的离线最低公共祖先算法。