java - 此处用 Java 实现的二叉树中 LCA 的时间复杂度是多少

Question

我有这段代码可以在二叉树中找到两个节点的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) 中找到最小公共(public)祖先，其中 h 是树的高度，即 O(log n)如果树是平衡的。

最后的评论 - 如果您正在准备比赛或面试，请确保处理极端情况。您的代码不处理其中一个节点不包含在树中的情况。