1

我有这段代码可以least common Ancestor在nodes. binary tree我认为时间复杂度是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;
        }
4

2 回答 2

2

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

最后的评论 - 如果你正在准备比赛或面试，请务必注意极端情况。您的代码不处理树中不包含节点之一的情况。

于 2014-01-29T07:59:29.750 回答
0

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

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

于 2014-01-29T06:36:46.397 回答