我有这段代码可以在二叉树
中找到两个节点
的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;
}
最佳答案
你的代码的时间复杂度是O(n)
,因为你正在遍历整棵树,即你正在访问它的所有节点。但是,如果您没有 BST,而只有一棵二叉树,那么这是您在父节点上没有指针的情况下可以实现的最好结果(在这种情况下,构建从两个节点到根节点的路径并返回一个节点是在两条路径中)。如果你有 BST,那么你可以定位两个节点并在 O(h)
中找到最小公共(public)祖先,其中 h 是树的高度,即 O(log n)
如果树是平衡的。
最后的评论 - 如果您正在准备比赛或面试,请确保处理极端情况。您的代码不处理其中一个节点不包含在树中的情况。
关于java - 此处用 Java 实现的二叉树中 LCA 的时间复杂度是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21423444/