Как найти наименьшего общего предка двух узлов в любом двоичном дереве?

Двоичное дерево здесь не обязательно может быть двоичным деревом поиска.
Структура может быть принята как -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

Максимальное решение, которое я мог бы разработать с другом, было что-то в этом роде.
Рассмотрим это двоичное дерево :

Выход по обходу по порядку - 8, 4, 9, 2, 5, 1, 6, 3, 7

А доходность прохождения заказа - 8, 9, 4, 5, 2, 6, 7, 3, 1

Так, например, если мы хотим найти общего предка узлов 8 и 5, то мы составим список всех узлов, которые находятся между 8 и 5 в обходе дерева порядков, которое в этом случае оказывается [4, 9 , 2]. Затем мы проверяем, какой узел в этом списке появляется последним в обходе после заказа, а это 2. Следовательно, общий предок для 8 и 5 равен 2.

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

Но это очень грубый подход, и я не уверен, что он сломается в каком-то случае. Есть ли другое (возможно, более оптимальное) решение этой проблемы?

Ник Джонсон прав, что алгоритм временной сложности O (n) - это лучшее, что вы можете сделать, если у вас нет родительских указателей.) Для простой рекурсивной версии этого алгоритма см. Код в посте Киндинга, который выполняется за время O (n). ,

Но имейте в виду, что если у ваших узлов есть родительские указатели, возможен улучшенный алгоритм. Для обоих рассматриваемых узлов создайте список, содержащий путь от корня до узла, начиная с узла и вставляя спереди родительский элемент.

Таким образом, для 8 в вашем примере вы получаете (показывая шаги): {4}, {2, 4}, {1, 2, 4}

Сделайте то же самое для вашего другого рассматриваемого узла, в результате чего (шаги не показаны): {1, 2}

Теперь сравните два списка, которые вы создали, ища первый элемент, в котором список отличается, или последний элемент одного из списков, в зависимости от того, что произойдет раньше.

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

Независимо от того, как построено дерево, если это будет операция, которую вы выполняете над деревом много раз без изменения между ними, есть другие алгоритмы, которые вы можете использовать, которые требуют подготовки O (n) [linear] time, но затем находят любой пара занимает только O (1) [постоянное] время. Ссылки на эти алгоритмы см. На самой низкой странице общих предков в Википедии . (Благодарим Джейсона за оригинальную публикацию этой ссылки)

Начиная с rootузла и двигаясь вниз, если вы обнаружите какой-либо узел, который имеет одного pили qкак его прямого потомка, то это LCA. (edit - это должно быть, если pили qявляется значением узла, вернуть его. В противном случае произойдет сбой, когда один из pили qявляется прямым потомком другого.)

Иначе, если вы найдете узел с pего правым (или левым) поддеревом и qего левым (или правым) поддеревом, то это LCA.

Исправленный код выглядит так:

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Приведенный ниже код завершается ошибкой, когда один из них является прямым потомком другого.

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is direct child of root then root is LCA.
        if(root->left==p || root->left==q || 
           root->right ==p || root->right ==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Код в действии

Вот рабочий код в JAVA

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

Ответы, данные до сих пор, используют рекурсию или хранят, например, путь в памяти.

Оба этих подхода могут потерпеть неудачу, если у вас очень глубокое дерево.

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

Вот код:

findLowestCommonAncestor(v,w):
  depth_vv = depth(v);
  depth_ww = depth(w);

  vv = v; 
  ww = w;

  while( depth_vv != depth_ww ) {
    if ( depth_vv > depth_ww ) {
      vv = parent(vv);
      depth_vv--;
    else {
      ww = parent(ww);
      depth_ww--;
    }
  }

  while( vv != ww ) {
    vv = parent(vv);
    ww = parent(ww);
  }

  return vv;    

Временная сложность этого алгоритма: O (n). Пространственная сложность этого алгоритма: O (1).

Что касается вычисления глубины, мы можем сначала вспомнить определение: если v - корень, глубина (v) = 0; В противном случае глубина (v) = глубина (родитель (v)) + 1. Мы можем вычислить глубину следующим образом:

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;

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

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

Это можно найти по адресу: - http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

 tree_node_type *LowestCommonAncestor(
 tree_node_type *root , tree_node_type *p , tree_node_type *q)
 {
     tree_node_type *l , *r , *temp;
     if(root==NULL)
     {
        return NULL;
     }

    if(root->left==p || root->left==q || root->right ==p || root->right ==q)
    {
        return root;
    }
    else
    {
        l=LowestCommonAncestor(root->left , p , q);
        r=LowestCommonAncestor(root->right , p, q);

        if(l!=NULL && r!=NULL)
        {
            return root;
        }
        else
        {
        temp = (l!=NULL)?l:r;
        return temp;
        }
    }
}

Автономный алгоритм наименее общих предков Тарьяна достаточно хорош (см. Также Википедию ). Есть больше о проблеме (самой низкой общей проблеме предка) в Википедии .

Чтобы узнать общего предка двух узлов:

• Найдите указанный узел Node1 в дереве с помощью бинарного поиска и сохраните все узлы, посещенные в этом процессе, в массиве, скажем, A1. Время - O (logn), Пространство - O (logn)
• Найдите указанный Node2 в дереве с помощью бинарного поиска и сохраните все узлы, посещенные в этом процессе, в массиве, скажем, A2. Время - O (logn), Пространство - O (logn)
• Если список А1 или список А2 пуст, то один узел не существует, поэтому общего предка нет.
• Если список А1 и список А2 не пусты, смотрите в список, пока не найдете несоответствующий узел. Как только вы найдете такой узел, то предшествующий ему узел станет общим предком.

Это будет работать для бинарного дерева поиска.

Я сделал попытку с иллюстративными картинками и рабочим кодом на Java,

http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html

Приведенный ниже рекурсивный алгоритм будет работать в O (log N) для сбалансированного двоичного дерева. Если какой-либо из узлов, переданных в функцию getLCA (), совпадает с корневым, то корневым будет LCA, и не будет необходимости выполнять какую-либо проверку.

Тестовые случаи. [1] Оба узла n1 и n2 находятся в дереве и находятся по обе стороны от их родительского узла. [2] Либо узел n1, либо n2 является корнем, а LCA - корнем. [3] В дереве есть только n1 или n2, LCA будет либо корневым узлом левого поддерева корня дерева, либо LCA будет корневым узлом правого поддерева корня дерева.

[4] Ни n1, ни n2 нет в дереве, здесь нет LCA. [5] Оба n1 и n2 находятся на одной прямой рядом друг с другом, LCA будет либо n1, либо n2, который всегда находится близко к корню дерева.

//find the search node below root
bool findNode(node* root, node* search)
{
    //base case
    if(root == NULL)
        return false;

    if(root->val == search->val)
        return true;

    //search for the node in the left and right subtrees, if found in either return true
    return (findNode(root->left, search) || findNode(root->right, search));
}

//returns the LCA, n1 & n2 are the 2 nodes for which we are
//establishing the LCA for
node* getLCA(node* root, node* n1, node* n2)
{
    //base case
    if(root == NULL)
        return NULL;

    //If 1 of the nodes is the root then the root is the LCA
    //no need to recurse.
    if(n1 == root || n2 == root)
        return root;

    //check on which side of the root n1 and n2 reside
    bool n1OnLeft = findNode(root->left, n1);
    bool n2OnLeft = findNode(root->left, n2);

    //n1 & n2 are on different sides of the root, so root is the LCA
    if(n1OnLeft != n2OnLeft)
        return root;

    //if both n1 & n2 are on the left of the root traverse left sub tree only
    //to find the node where n1 & n2 diverge otherwise traverse right subtree
    if(n1OnLeft)
        return getLCA(root->left, n1, n2);
    else
        return getLCA(root->right, n1, n2);
}

Просто идите вниз от всего дерева, rootпока оба заданных узла, скажем, pи q, для которых должен быть найден Ancestor, находятся в одном поддереве (то есть их значения меньше или оба больше, чем у корня).

Это идет прямо от корня до Наименьшего Общего Предка, не смотря на остальную часть дерева, так что это в значительной степени так же быстро, как и доходит. Несколько способов сделать это.

Итеративный, O (1) пространство

питон

def lowestCommonAncestor(self, root, p, q):
    while (root.val - p.val) * (root.val - q.val) > 0:
        root = (root.left, root.right)[p.val > root.val]
    return root

Ява

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    return root;
}

в случае переполнения я бы сделал (root.val - (long) p.val) * (root.val - (long) q.val)

рекурсивный

питон

def lowestCommonAncestor(self, root, p, q):
    next = p.val < root.val > q.val and root.left or \
           p.val > root.val < q.val and root.right
    return self.lowestCommonAncestor(next, p, q) if next else root

Ява

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return (root.val - p.val) * (root.val - q.val) < 1 ? root :
           lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Рассмотрим это дерево

Если мы проведем обход по порядку и по предзаказу и найдем первого общего предшественника и преемника, мы получим общего предка.

предварительный заказ => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 предварительный заказ => 7,3,1,0,2,6,4 , 5,12,9,8,11,10,13,15,14

• например: 1

Наименее общий предок 8,11

в предзаказе имеем => 9,14,15,13,12,7 после 8 и 11 в предзаказе имеем => 7,3,1,0,2,6,4,5,12,9 до 8 и 11

9 - это первое общее число, которое встречается после 8 и 11 в предварительном заказе и до 8 и 11 в предварительном заказе, следовательно, 9 является ответом

• например: 2

Наименее общий предок 5,10

11,9,14,15,13,12,7 в почтовом заказе 7,3,1,0,2,6,4 в предварительном заказе

7 является первым числом, которое встречается после 5,10 в предварительном заказе и до 5,10 в предварительном заказе, следовательно, 7 является ответом

Если это полное двоичное дерево с дочерними узлами x, равными 2 * x и 2 * x + 1, то есть более быстрый способ сделать это

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;  
}

Как это работает

1. получить биты, необходимые для представления x & y, который с помощью двоичного поиска равен O (log (32))
2. общий префикс двоичной записи x & y является общим предком
3. в зависимости от того, что больше, ни один из битов не переводится в тот же бит с помощью k >> diff
4. k = x ^ y стирает общий префикс x & y
5. найти биты, представляющие оставшийся суффикс
6. сдвиньте x или y на суффиксные биты, чтобы получить общий префикс, который является общим предком.

Это работает, потому что в основном рекурсивно делит большее число на два, пока оба числа не станут равными. Это число является общим предком. Разделение фактически является операцией правильного сдвига. Поэтому нам нужно найти общий префикс из двух чисел, чтобы найти ближайшего предка

В Scala вы можете:

  abstract class Tree
  case class Node(a:Int, left:Tree, right:Tree) extends Tree
  case class Leaf(a:Int) extends Tree

  def lca(tree:Tree, a:Int, b:Int):Tree = {
    tree match {
      case Node(ab,l,r) => {
        if(ab==a || ab ==b) tree else {
          val temp = lca(l,a,b);
          val temp2 = lca(r,a,b);
          if(temp!=null && temp2 !=null)
            tree
          else if (temp==null && temp2==null)
            null
          else if (temp==null) r else l
        }

      }
      case Leaf(ab) => if(ab==a || ab ==b) tree else null
    }
  }

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        return left == null ? right : right == null ? left : root;
    }

Вот способ C ++ сделать это. Постарались сделать алгоритм максимально простым для понимания:

// Assuming that `BinaryNode_t` has `getData()`, `getLeft()` and `getRight()`
class LowestCommonAncestor
{
  typedef char type;    
  // Data members which would behave as place holders
  const BinaryNode_t* m_pLCA;
  type m_Node1, m_Node2;

  static const unsigned int TOTAL_NODES = 2;

  // The core function which actually finds the LCA; It returns the number of nodes found
  // At any point of time if the number of nodes found are 2, then it updates the `m_pLCA` and once updated, we have found it!
  unsigned int Search (const BinaryNode_t* const pNode)
  {
    if(pNode == 0)
      return 0;

    unsigned int found = 0;

    found += (pNode->getData() == m_Node1);
    found += (pNode->getData() == m_Node2);

    found += Search(pNode->getLeft()); // below condition can be after this as well
    found += Search(pNode->getRight());

    if(found == TOTAL_NODES && m_pLCA == 0)
      m_pLCA = pNode;  // found !

    return found;
  }

public:
  // Interface method which will be called externally by the client
  const BinaryNode_t* Search (const BinaryNode_t* const pHead,
                              const type node1,
                              const type node2)
  {
    // Initialize the data members of the class
    m_Node1 = node1;
    m_Node2 = node2;
    m_pLCA = 0;

    // Find the LCA, populate to `m_pLCANode` and return
    (void) Search(pHead);
    return m_pLCA;
  }
};

Как это использовать:

LowestCommonAncestor lca;
BinaryNode_t* pNode = lca.Search(pWhateverBinaryTreeNodeToBeginWith);
if(pNode != 0)
  ...

Самый простой способ найти самого низкого общего предка - использовать следующий алгоритм:

Исследовать корневой узел

если значение1 и значение2 строго меньше значения в корневом узле 
    Изучить левое поддерево
иначе, если value1 и value2 строго больше, чем значение в корневом узле 
    Изучите правильное поддерево
еще
    вернуть корень

public int LCA(TreeNode root, int value 1, int value 2) {
    while (root != null) {
       if (value1 < root.data && value2 < root.data)
           return LCA(root.left, value1, value2);
       else if (value2 > root.data && value2 2 root.data)
           return LCA(root.right, value1, value2);
       else
           return root
    }

    return null;
} 

Я нашел решение

1. Принять заказ
2. Принять предварительный заказ
3. Принять заказ

В зависимости от 3 обходов, вы можете решить, кто является LCA. От LCA найдите расстояние обоих узлов. Добавьте эти два расстояния, что является ответом.

Вот что я думаю,

1. Найдите маршрут для первого узла, сохраните его в arr1.
2. Начните находить маршрут для узла 2, проверяя каждое значение от корня до arr1.
3. время, когда значение отличается, выход. Старое сопоставленное значение - это LCA.

Сложность: шаг 1: O (n), шаг 2 = ~ O (n), всего = ~ O (n).

Вот два подхода в c # (.net) (оба обсуждались выше) для справки:

1. Рекурсивная версия поиска LCA в двоичном дереве (O (N) - так как самое большее посещается каждый узел) (основные точки решения - это то, что LCA - это (a) единственный узел в двоичном дереве, где оба элемента находятся по обе стороны от поддеревьев (слева) и справа) это LCA. (b) И также не имеет значения, какой узел присутствует с обеих сторон - изначально я пытался сохранить эту информацию, и, очевидно, рекурсивная функция стала настолько запутанной. Как только я понял это, она стала очень элегантной.

2. Поиск по обоим узлам (O (N)) и отслеживание путей (использует дополнительное пространство - поэтому, # 1, вероятно, лучше, даже если пространство, вероятно, незначительно, если двоичное дерево хорошо сбалансировано, так как тогда дополнительное потребление памяти будет только в O (журнал (N)).

   так что пути сравниваются (по сути, аналогично принятому ответу - но пути рассчитываются, если предположить, что указательный узел отсутствует в узле двоичного дерева)

3. Только для завершения ( не относится к вопросу ), LCA в BST (O (log (N))

4. тесты

рекурсивные:

private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode, 
            int e1, int e2)
        {
            Debug.Assert(e1 != e2);
            
            if(treeNode == null)
            {
                return null;
            }
            if((treeNode.Element == e1)
                || (treeNode.Element == e2))
            {
                //we don't care which element is present (e1 or e2), we just need to check 
                //if one of them is there
                return treeNode;
            }
            var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2);
            var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2);
            if(nLeft != null && nRight != null)
            {
                //note that this condition will be true only at least common ancestor
                return treeNode;
            }
            else if(nLeft != null)
            {
                return nLeft;
            }
            else if(nRight != null)
            {
                return nRight;
            }
            return null;
        }

где выше частная рекурсивная версия вызывается следующим публичным методом:

public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2)
        {
            var n = this.FindNode(this._root, e1);
            if(null == n)
            {
                throw new Exception("Element not found: " + e1);
            }
            if (e1 == e2)
            {   
                return n;
            }
            n = this.FindNode(this._root, e2);
            if (null == n)
            {
                throw new Exception("Element not found: " + e2);
            }
            var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2);
            if (null == node)
            {
                throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2));
            }
            return node;
        }

Решение путем отслеживания путей обоих узлов:

public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2)
        {
            var path1 = new List<BinaryTreeNode>();
            var node1 = this.FindNodeAndPath(this._root, e1, path1);
            if(node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e1));
            }
            if(e1 == e2)
            {
                return node1;
            }
            List<BinaryTreeNode> path2 = new List<BinaryTreeNode>();
            var node2 = this.FindNodeAndPath(this._root, e2, path2);
            if (node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e2));
            }
            BinaryTreeNode lca = null;
            Debug.Assert(path1[0] == this._root);
            Debug.Assert(path2[0] == this._root);
            int i = 0;
            while((i < path1.Count)
                && (i < path2.Count)
                && (path2[i] == path1[i]))
            {
                lca = path1[i];
                i++;
            }
            Debug.Assert(null != lca);
            return lca;
        }

где FindNodeAndPath определяется как

private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path)
        {
            if(node == null)
            {
                return null;
            }
            if(node.Element == e)
            {
                path.Add(node);
                return node;
            }
            var n = this.FindNodeAndPath(node.Left, e, path);
            if(n == null)
            {
                n = this.FindNodeAndPath(node.Right, e, path);
            }
            if(n != null)
            {
                path.Insert(0, node);
                return n;
            }
            return null;
        }

BST (LCA) - не связано (только для завершения для справки)

public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
        {
            //ensure both elements are there in the bst
            var n1 = this.BstFind(e1, throwIfNotFound: true);
            if(e1 == e2)
            {
                return n1;
            }
            this.BstFind(e2, throwIfNotFound: true);
            BinaryTreeNode leastCommonAcncestor = this._root;
            var iterativeNode = this._root;
            while(iterativeNode != null)
            {
                if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
                {
                    iterativeNode = iterativeNode.Left;
                }
                else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
                {
                    iterativeNode = iterativeNode.Right;
                }
                else
                {
                    //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                    return iterativeNode;
                }
            }
            //control will never come here
            return leastCommonAcncestor;
        }

Модульные тесты

[TestMethod]
        public void LeastCommonAncestorTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
            }
            for(int i = 0; i < b.Length; i++)
            {
                var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
                Assert.IsTrue(n.Element == b[i]);
                var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]);
                Assert.IsTrue(n1.Element == b[i]);
                Assert.IsTrue(n == n1);
                var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]);
                Assert.IsTrue(n2.Element == b[i]);
                Assert.IsTrue(n2 == n1);
                Assert.IsTrue(n2 == n);
            }
        }

Если кто-то заинтересован в псевдокоде (для университетских домашних работ), вот один.

GETLCA(BINARYTREE BT, NODE A, NODE  B)
IF Root==NIL
    return NIL
ENDIF

IF Root==A OR root==B
    return Root
ENDIF

Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)

IF Left! = NIL AND Right! = NIL
    return root
ELSEIF Left! = NIL
    Return Left
ELSE
    Return Right
ENDIF

Хотя на этот вопрос уже был дан ответ, это мой подход к этой проблеме с использованием языка программирования C. Хотя код показывает двоичное дерево поиска (что касается insert ()), алгоритм работает и для двоичного дерева. Идея состоит в том, чтобы обойти все узлы, которые лежат от узла A к узлу B при обходе по порядку, и искать их индексы в обходе по порядку. Узел с максимальным индексом в прохождении после заказа является самым низким общим предком.

Это рабочий код C для реализации функции по нахождению наименьшего общего предка в двоичном дереве. Я также предоставляю все функции утилит и т. Д., Но для быстрого понимания перейдем к CommonAncestor ().

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

static inline int min (int a, int b)
{
    return ((a < b) ? a : b);
}
static inline int max (int a, int b)
{
    return ((a > b) ? a : b);
}

typedef struct node_ {
    int value;
    struct node_ * left;
    struct node_ * right;
} node;

#define MAX 12

int IN_ORDER[MAX] = {0};
int POST_ORDER[MAX] = {0};

createNode(int value) 
{
    node * temp_node = (node *)malloc(sizeof(node));
    temp_node->left = temp_node->right = NULL;
    temp_node->value = value;
    return temp_node;
}

node *
insert(node * root, int value)
{
    if (!root) {
        return createNode(value);
    }

    if (root->value > value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }

    return root;
}


/* Builds inorder traversal path in the IN array */
void
inorder(node * root, int * IN)
{
    static int i = 0;

    if (!root) return;

    inorder(root->left, IN);
    IN[i] = root->value;
    i++;
    inorder(root->right, IN);
}

/* Builds post traversal path in the POST array */

void
postorder (node * root, int * POST)
{
    static int i = 0;

    if (!root) return;

    postorder(root->left, POST);
    postorder(root->right, POST);
    POST[i] = root->value;
    i++;
}


int
findIndex(int * A, int value)
{
    int i = 0;
    for(i = 0; i< MAX; i++) {
        if(A[i] == value) return i;
    }
}
int
CommonAncestor(int val1, int val2)
{
    int in_val1, in_val2;
    int post_val1, post_val2;
    int j=0, i = 0; int max_index = -1;

    in_val1 = findIndex(IN_ORDER, val1);
    in_val2 = findIndex(IN_ORDER, val2);
    post_val1 = findIndex(POST_ORDER, val1);
    post_val2 = findIndex(POST_ORDER, val2);

    for (i = min(in_val1, in_val2); i<= max(in_val1, in_val2); i++) {
        for(j = 0; j < MAX; j++) {
            if (IN_ORDER[i] == POST_ORDER[j]) {
                if (j > max_index) {
                    max_index = j;
                }
            }
        }
    }
    printf("\ncommon ancestor of %d and %d is %d\n", val1, val2, POST_ORDER[max_index]);
    return max_index;
}
int main()
{
    node * root = NULL; 

    /* Build a tree with following values */
    //40, 20, 10, 30, 5, 15, 25, 35, 1, 80, 60, 100
    root = insert(root, 40);
    insert(root, 20);
    insert(root, 10);
    insert(root, 30);
    insert(root, 5);
    insert(root, 15);
    insert(root, 25);
    insert(root, 35);
    insert(root, 1);
    insert(root, 80);
    insert(root, 60);
    insert(root, 100);

    /* Get IN_ORDER traversal in the array */
    inorder(root, IN_ORDER);

    /* Get post order traversal in the array */
    postorder(root, POST_ORDER);

    CommonAncestor(1, 100);


}

Может быть еще один подход. Однако это не так эффективно, как тот, который уже предлагался в ответах.

• Создайте вектор пути для узла n1.

• Создайте второй вектор пути для узла n2.

• Вектор пути, подразумевающий множество узлов из этого, будет проходить до нужного узла.

• Сравните оба вектора пути. Индекс, где они не совпадают, возвращает узел с этим индексом - 1. Это даст LCA.

Минусы для этого подхода:

Необходимо пересечь дерево дважды для расчета векторов пути. Нужно дополнительное пространство O (h) для хранения векторов пути.

Однако это легко реализовать и понять.

Код для расчета вектора пути:

private boolean findPathVector (TreeNode treeNode, int key, int pathVector[], int index) {

        if (treeNode == null) {
            return false;
        }

        pathVector [index++] = treeNode.getKey ();

        if (treeNode.getKey () == key) {
            return true;
        }
        if (findPathVector (treeNode.getLeftChild (), key, pathVector, index) || 
            findPathVector (treeNode.getRightChild(), key, pathVector, index)) {

            return true;        
        }

        pathVector [--index] = 0;
        return false;       
    }

Попробуй вот так

node * lca(node * root, int v1,int v2)
{

if(!root) {
            return NULL;
    }
    if(root->data == v1 || root->data == v2) {
        return root;}
    else
    {
        if((v1 > root->data && v2 < root->data) || (v1 < root->data && v2 > root->data))
        {
            return root;
        }

        if(v1 < root->data && v2 < root->data)
        {
            root = lca(root->left, v1, v2);
        }

        if(v1 > root->data && v2 > root->data)
        {
            root = lca(root->right, v1, v2);
        }
    }
return root;
}

Грубый путь:

• На каждом узле
  • X = найти, если любой из n1, n2 существует на левой стороне узла
  • Y = найти, если любой из n1, n2 существует на правой стороне узла
    • если сам узел n1 || n2, мы можем назвать его найденным слева или справа в целях обобщения.
  • Если X и Y истинны, то узлом является CA

Проблема описанного выше метода заключается в том, что мы будем выполнять поиск несколько раз, то есть существует вероятность, что каждый узел будет проходить несколько раз. Мы можем преодолеть эту проблему, если сможем записать информацию, чтобы не обрабатывать ее снова (подумайте о динамическом программировании).

Поэтому вместо того, чтобы находить каждый узел, мы ведем запись того, что уже найдено.

Лучший способ:

• Мы проверяем, является ли для данного узла left_set (имеется в виду, что n1 | n2 было найдено в левом поддереве) или right_set в глубине первым способом. (ПРИМЕЧАНИЕ: мы даем самому корню свойство быть left_set, если оно равно n1 | n2)
• Если и left_set, и right_set, то узел является LCA.

Код:

struct Node *
findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) {
   int left_set, right_set;
   left_set = right_set = 0;
   struct Node *leftCA, *rightCA;
   leftCA = rightCA = NULL;

   if (root == NULL) {
      return NULL;
   }
   if (root == n1 || root == n2) {
      left_set = 1;
      if (n1 == n2) {
         right_set = 1;
      }
   }

   if(!left_set) {
      leftCA = findCA(root->left, n1, n2, &left_set);
      if (leftCA) {
         return leftCA;
      }
   }
   if (!right_set) {
      rightCA= findCA(root->right, n1, n2, &right_set);
      if(rightCA) {
         return rightCA;
      }
   }

   if (left_set && right_set) {
      return root;
   } else {
      *set = (left_set || right_set);
      return NULL;
   }
}

Код для поиска в ширину, чтобы убедиться, что оба узла находятся в дереве. Только тогда двигайтесь вперед с поиском LCA. Пожалуйста, прокомментируйте, если у вас есть предложения по улучшению. Я думаю, что мы, вероятно, можем пометить их как посещенных и возобновить поиск в определенной точке, где мы остановились, чтобы улучшить для второго узла (если он не найден, ПОСЕТИЛ)

public class searchTree {
    static boolean v1=false,v2=false;
    public static boolean bfs(Treenode root, int value){
         if(root==null){
           return false;
     }
    Queue<Treenode> q1 = new LinkedList<Treenode>();

    q1.add(root);
    while(!q1.isEmpty())
    {
        Treenode temp = q1.peek();

        if(temp!=null) {
            q1.remove();
            if (temp.value == value) return true;
            if (temp.left != null) q1.add(temp.left);
            if (temp.right != null) q1.add(temp.right);
        }
    }
    return false;

}
public static Treenode lcaHelper(Treenode head, int x,int y){

    if(head==null){
        return null;
    }

    if(head.value == x || head.value ==y){
        if (head.value == y){
            v2 = true;
            return head;
        }
        else {
            v1 = true;
            return head;
        }
    }

    Treenode left = lcaHelper(head.left, x, y);
    Treenode right = lcaHelper(head.right,x,y);

    if(left!=null && right!=null){
        return head;
    }
    return (left!=null) ? left:right;
}

public static int lca(Treenode head, int h1, int h2) {
    v1 = bfs(head,h1);
    v2 = bfs(head,h2);
    if(v1 && v2){
        Treenode lca = lcaHelper(head,h1,h2);
        return lca.value;
    }
    return -1;
}
}

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

Обходной подход путь Предположим, что вы находите LCA для узлов A и B, самый простой подход заключается в том, чтобы сначала получить путь от корня к A, а затем получить путь от корня к B. После того, как вы получите эти два пути, вы можете легко перебрать их и найдите последний общий узел, который является самым низким общим предком A и B.

Рекурсивное решение Другой подход заключается в использовании рекурсии. Во-первых, мы можем получить LCA как из левого, так и из правого дерева (если оно существует). Если любой из A или B является корневым узлом, тогда корень - это LCA, и мы просто возвращаем корень, который является конечной точкой рекурсии. Поскольку мы продолжаем делить дерево на поддеревья, в конечном итоге мы попадем либо в А, либо в В.

Чтобы объединить решения подзадач, если LCA (левое дерево) возвращает узел, мы знаем, что и A, и B находятся в левом дереве, и возвращаемый узел является конечным результатом. Если LCA (слева) и LCA (справа) возвращают непустые узлы, это означает, что A и B находятся в левом и правом дереве соответственно. В этом случае корневой узел является самым низким общим узлом.

Проверьте Lowest Common Ancestor для детального анализа и решения.

Некоторые решения здесь предполагают, что есть ссылка на корневой узел, некоторые предполагают, что дерево является BST. Совместное использование моего решения с использованием hashmap без ссылки на rootузел и дерево может быть BST или не BST:

    var leftParent : Node? = left
    var rightParent : Node? = right
    var map = [data : Node?]()

    while leftParent != nil {
        map[(leftParent?.data)!] = leftParent
        leftParent = leftParent?.parent
    }

    while rightParent != nil {
        if let common = map[(rightParent?.data)!] {
            return common
        }
        rightParent = rightParent?.parent
    }

Решение 1: Рекурсивно - Быстрее

• Идея состоит в том, чтобы пройти дерево, начиная с корня. Если любой из заданных ключей p и q совпадает с root, тогда root - это LCA, при условии, что оба ключа присутствуют. Если root не совпадает ни с одним из ключей, мы выбираем левое и правое поддерево.
• Узлом, который имеет один ключ, присутствующий в его левом поддереве, а другой ключ, присутствующий в правом поддереве, является LCA. Если оба ключа лежат в левом поддереве, то левое поддерево также имеет LCA, в противном случае LCA лежит в правом поддереве.

• Сложность времени: O (n)
• Сложность пространства: O (h) - для рекурсивного стека вызовов

class Solution 
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if(root == null || root == p  || root == q)
            return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null)
            return right;
        else if(right == null)
            return left;
        else
            return root;    // If(left != null && right != null)
    }
}

Решение 2: Итеративное - Использование родительских указателей - Медленнее

• Создайте пустую хеш-таблицу.
• Вставьте p и всех его предков в хеш-таблицу.
• Проверьте, существует ли q или любой из его предков в хеш-таблице, если да, верните первого существующего предка.

• Сложность времени: O (n) - в худшем случае мы можем посещать все узлы двоичного дерева.
• Сложность пространства: O (n) - Пространство, использующее родительский указатель Hash-таблица, ancestor_set и queue, будет O (n) каждый.

class Solution
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
        HashSet<TreeNode> ancestors_set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();

        parent_map.put(root, null);
        queue.add(root);

        while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
        {
            TreeNode node = queue.poll();

            if(node.left != null)
            {
                parent_map.put(node.left, node);
                queue.add(node.left);
            }
            if(node.right != null)
            {
                parent_map.put(node.right, node);
                queue.add(node.right);
            }
        }

        while(p != null)
        {
            ancestors_set.add(p);
            p = parent_map.get(p);
        }

        while(!ancestors_set.contains(q))
            q = parent_map.get(q);

        return q;
    }
}