Какая временная сложность для LCA в бинарном дереве, реализованном в Java здесь

Question

У меня есть этот код, чтобы найти 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;
        }

Answer 1

Временная сложность вашего кода O(n)потому что вы пересекаете все дерево, то есть вы посещаете все его узлы. Однако, если у вас нет BST, а есть только двоичное дерево, это лучшее, чего вы можете достичь, не имея указателя на родительский узел (в этом случае создайте пути от обоих узлов до корневого узла и верните узел, который является в обоих направлениях). Если у вас есть BST, то вы можете найти оба узла и найти наименее общего предка в O(h)где h высота дерева, и это O(log n) если дерево сбалансировано.

Заключительное замечание - если вы готовитесь к конкурсу или собеседованию, обязательно позаботьтесь о ключевых случаях. Ваш код не обрабатывает случай, когда один из узлов не содержится в дереве.

Answer 2

Я уверен, что это работает в O (n) потому что вы проходите через весь граф (то есть в каждом узле вы идете в обоих направлениях - вправо и влево).

Я бы предложил прочитать алгоритм самых низких общих предков Тарьяна.