Bagaimana menemukan leluhur umum terendah dari dua simpul di pohon biner?

Binary Tree di sini mungkin belum tentu menjadi Binary Search Tree.
Struktur dapat diambil sebagai -

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

Solusi maksimal yang bisa saya selesaikan dengan seorang teman adalah sesuatu seperti ini -
Pertimbangkan pohon biner ini :

Invers traversal menghasilkan - 8, 4, 9, 2, 5, 1, 6, 3, 7

Dan hasil postorder traversal - 8, 9, 4, 5, 2, 6, 7, 3, 1

Jadi misalnya, jika kita ingin menemukan leluhur umum dari node 8 dan 5, maka kita membuat daftar semua node yang berada di antara 8 dan 5 di traversal pohon inorder, yang dalam hal ini kebetulan [4, 9 , 2]. Kemudian kami memeriksa simpul mana dalam daftar ini yang muncul terakhir dalam postorder traversal, yaitu 2. Oleh karena itu leluhur bersama untuk 8 dan 5 adalah 2.

Kompleksitas untuk algoritma ini, saya percaya adalah O (n) (O (n) untuk travers inorder / postorder, sisa langkah lagi menjadi O (n) karena mereka tidak lebih dari iterasi sederhana dalam array). Tetapi ada peluang kuat bahwa ini salah. :-)

Tapi ini pendekatan yang sangat kasar, dan saya tidak yakin apakah itu rusak untuk beberapa kasus. Apakah ada solusi lain (mungkin lebih optimal) untuk masalah ini?

Nick Johnson benar bahwa algoritma kompleksitas waktu O (n) adalah yang terbaik yang dapat Anda lakukan jika Anda tidak memiliki orangtua pointer.) Untuk versi rekursif sederhana dari algoritma tersebut lihat kode di posting Kinding yang berjalan dalam waktu O (n) waktu .

Tetapi perlu diingat bahwa jika node Anda memiliki pointer orangtua, algoritma yang ditingkatkan dimungkinkan. Untuk kedua node yang dimaksud buatlah daftar yang berisi path dari root ke node dengan mulai dari node, dan masukkan induk ke depan.

Jadi untuk 8 dalam contoh Anda, Anda mendapatkan (menunjukkan langkah-langkah): {4}, {2, 4}, {1, 2, 4}

Lakukan hal yang sama untuk node Anda yang lain dalam pertanyaan, menghasilkan (langkah-langkah tidak ditampilkan): {1, 2}

Sekarang bandingkan dua daftar yang Anda buat mencari elemen pertama di mana daftar berbeda, atau elemen terakhir dari salah satu daftar, mana yang lebih dulu.

Algoritma ini membutuhkan waktu O (h) di mana h adalah ketinggian pohon. Dalam kasus terburuk O (h) setara dengan O (n), tetapi jika pohon seimbang, itu hanya O (log (n)). Ini juga membutuhkan ruang O (h). Versi yang disempurnakan adalah mungkin yang hanya menggunakan ruang konstan, dengan kode yang ditunjukkan pada posting CEGRD

Terlepas dari bagaimana pohon dibangun, jika ini akan menjadi operasi yang Anda lakukan berkali-kali pada pohon tanpa mengubahnya di antara, ada algoritma lain yang dapat Anda gunakan yang memerlukan persiapan waktu O (n) [linear], tetapi kemudian menemukan pasangan hanya membutuhkan waktu O (1) [konstan]. Untuk referensi algoritma ini, lihat halaman masalah leluhur umum terendah di Wikipedia . (Kredit ke Jason untuk awalnya memposting tautan ini)

Mulai dari rootnode dan bergerak ke bawah jika Anda menemukan node yang memiliki patau qsebagai anak langsung maka itu adalah LCA. (edit - ini seharusnya jika patau qmerupakan nilai node, kembalikan. Jika tidak, akan gagal ketika salah satu patauq merupakan anak langsung dari yang lain.)

Lain jika Anda menemukan node dengan psubtree kanan (atau kiri) danq kiri (atau kanan) maka itu adalah LCA.

Kode tetap terlihat seperti:

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;
                }
        }
}

Kode di bawah ini gagal ketika salah satunya adalah anak langsung dari yang lain.

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;
                }
        }
}

Kode Beraksi

Berikut adalah kode yang berfungsi di JAWA

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; 
}

Jawaban yang diberikan sejauh ini menggunakan rekursi atau menyimpan, misalnya, jalur di memori.

Kedua pendekatan ini mungkin gagal jika Anda memiliki pohon yang sangat dalam.

Inilah pendapat saya tentang pertanyaan ini. Ketika kita memeriksa kedalaman (jarak dari akar) dari kedua node, jika keduanya sama, maka kita dapat dengan aman bergerak ke atas dari kedua node menuju leluhur yang sama. Jika salah satu dari kedalaman lebih besar maka kita harus bergerak ke atas dari simpul yang lebih dalam sambil tetap di yang lain.

Ini kodenya:

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;    

Kompleksitas waktu dari algoritma ini adalah: O (n). Kompleksitas ruang dari algoritma ini adalah: O (1).

Mengenai perhitungan kedalaman, pertama-tama kita dapat mengingat definisi: Jika v adalah root, depth (v) = 0; Kalau tidak, kedalaman (v) = kedalaman (induk (v)) + 1. Kita dapat menghitung kedalaman sebagai berikut:

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

Nah, jenis ini tergantung bagaimana Binary Tree Anda terstruktur. Agaknya Anda memiliki beberapa cara untuk menemukan simpul daun yang diinginkan mengingat akar pohon - cukup menerapkannya pada kedua nilai sampai cabang yang Anda pilih berbeda.

Jika Anda tidak memiliki cara untuk menemukan daun yang diinginkan diberikan root, maka satu-satunya solusi Anda - baik dalam operasi normal dan untuk menemukan simpul umum terakhir - adalah pencarian pohon dengan kekerasan.

Ini dapat ditemukan di: - 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;
        }
    }
}

Algoritma nenek moyang paling umum yang tidak umum dari Tarjan cukup baik (lih. Juga Wikipedia ) Ada lebih banyak tentang masalah (masalah leluhur umum terendah) di Wikipedia .

Untuk mengetahui leluhur umum dari dua simpul: -

• Temukan node yang diberikan Node1 di pohon menggunakan pencarian biner dan simpan semua node yang dikunjungi dalam proses ini dalam array katakanlah A1. Waktu - O (masuk), Spasi - O (masuk)
• Temukan Node2 yang diberikan di pohon menggunakan pencarian biner dan menyimpan semua node yang dikunjungi dalam proses ini dalam array mengatakan A2. Waktu - O (masuk), Spasi - O (masuk)
• Jika daftar A1 atau daftar A2 kosong maka satu node tidak ada sehingga tidak ada leluhur yang sama.
• Jika daftar A1 dan daftar A2 tidak kosong, lihat ke dalam daftar sampai Anda menemukan simpul yang tidak cocok. Segera setelah Anda menemukan simpul seperti itu maka simpul sebelum itu adalah leluhur yang sama.

Ini akan berfungsi untuk pohon pencarian biner.

Saya telah melakukan upaya dengan gambar ilustrasi dan kode kerja di Jawa,

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

Algoritma rekursif di bawah ini akan berjalan di O (log N) untuk pohon biner seimbang. Jika salah satu node yang dilewatkan ke fungsi getLCA () adalah sama dengan root maka root akan menjadi LCA dan tidak perlu melakukan recussrion.

Uji kasus. [1] Kedua node n1 & n2 berada di pohon dan berada di kedua sisi node induknya. [2] Entah simpul n1 atau n2 adalah root, LCA adalah root. [3] Hanya n1 atau n2 yang ada di pohon, LCA akan menjadi simpul akar subtree kiri dari root pohon, atau LCA akan menjadi simpul akar dari subtree kanan dari root pohon.

[4] Baik n1 atau n2 tidak ada di pohon, tidak ada LCA. [5] Baik n1 dan n2 berada dalam garis lurus di samping satu sama lain, LCA akan berupa n1 atau n2 yang pernah ditutup ke akar pohon.

//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);
}

Hanya berjalan turun dari seluruh pohon rootselama keduanya diberi node, katakan pdanq , untuk mana Leluhur harus ditemukan, berada di sub-pohon yang sama (artinya nilainya lebih kecil atau keduanya lebih besar dari pada root).

Ini berjalan langsung dari root ke Least Common Ancestor, tidak melihat sisa pohon, jadi cukup cepat. Beberapa cara untuk melakukannya.

Berulang, O (1) ruang

Python

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

Jawa

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;
}

jika terjadi overflow, saya akan melakukan (root.val - (long) p.val) * (root.val - (long) q.val)

Rekursif

Python

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

Jawa

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
}

Pertimbangkan pohon ini

Jika kita melakukan postorder dan preorder traversal dan menemukan pendahulu dan penerus umum yang terjadi pertama kali, kita mendapatkan leluhur yang sama.

postorder => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 preorder => 7,3,1,0,2,6,4 , 5,12,9,8,11,10,13,15,14

• misalnya: 1

Nenek moyang yang sama dari 8,11

dalam postorder kita memiliki => 9,14,15,13,12,7 setelah 8 & 11 di preorder kita memiliki => 7,3,1,0,2,6,4,5,12,9 sebelum 8 & 11

9 adalah angka umum pertama yang muncul setelah 8 & 11 di postorder dan sebelum 8 & 11 di preorder, maka 9 adalah jawabannya

• misalnya: 2

Nenek moyang yang sama dari 5,10

11,9,14,15,13,12,7 pada postorder 7,3,1,0,2,6,4 pada preorder

7 adalah angka pertama yang muncul setelah 5,10 pada postorder dan sebelum 5,10 pada preorder, maka 7 adalah jawabannya

Jika pohon penuh biner dengan anak-anak dari simpul x sebagai 2 * x dan 2 * x + 1 daripada ada cara yang lebih cepat untuk melakukannya

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;  
}

bagaimana cara kerjanya

1. dapatkan bit yang diperlukan untuk merepresentasikan x & y yang menggunakan pencarian biner adalah O (log (32))
2. awalan umum notasi biner dari x & y adalah leluhur yang sama
3. mana yang diwakili oleh tidak lebih besar dari bit dibawa ke bit yang sama oleh k >> diff
4. k = x ^ y memunculkan awalan umum x & y
5. temukan bit yang mewakili sufiks yang tersisa
6. menggeser x atau y dengan bit suffix untuk mendapatkan awalan umum yang merupakan nenek moyang yang sama.

Ini berfungsi karena pada dasarnya membagi angka yang lebih besar dengan dua secara rekursif sampai kedua angka sama. Angka itu adalah leluhur bersama. Membagi secara efektif adalah operasi shift yang tepat. Jadi kita perlu menemukan awalan umum dari dua angka untuk menemukan leluhur terdekat

Dalam scala, Anda dapat:

  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;
    }

Inilah cara C ++ untuk melakukannya. Telah mencoba untuk menjaga algoritma semudah mungkin untuk dipahami:

// 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;
  }
};

Bagaimana cara menggunakannya:

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

Cara termudah untuk menemukan Leluhur Biasa Terendah menggunakan algoritma berikut:

Periksa simpul akar

jika value1 dan value2 benar-benar kurang dari nilai pada simpul akar 
    Periksa subtree kiri
lain jika value1 dan value2 benar-benar lebih besar dari nilai pada simpul root 
    Periksa subtree kanan
lain
    kembali root

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;
} 

Saya menemukan solusinya

1. Ambil inorder
2. Ambil preorder
3. Ambil postorder

Bergantung pada 3 traversal, Anda dapat memutuskan siapa LCA. Dari LCA, cari jarak kedua node. Tambahkan dua jarak ini, yang merupakan jawabannya.

Inilah yang saya pikirkan,

1. Temukan rute untuk fist node, simpan ke arr1.
2. Mulailah menemukan rute untuk 2 simpul, sambil melakukan itu periksa setiap nilai dari root ke arr1.
3. saat nilai berbeda, keluar. Nilai yang cocok lama adalah LCA.

Kompleksitas: langkah 1: O (n), langkah 2 = ~ O (n), total = ~ O (n).

Berikut adalah dua pendekatan dalam c # (.net) (keduanya dibahas di atas) untuk referensi:

1. Versi rekursif menemukan LCA di pohon biner (O (N) - karena paling banyak setiap node dikunjungi) (poin utama dari solusi adalah LCA adalah (a) hanya simpul di pohon biner di mana kedua elemen berada di kedua sisi subtrees (kiri). dan kanan) adalah LCA. (b) Dan juga tidak masalah simpul mana yang hadir di kedua sisi - awalnya saya mencoba untuk menjaga info itu, dan jelas fungsi rekursif menjadi sangat membingungkan, setelah saya sadari, itu menjadi sangat elegan.

2. Pencarian kedua node (O (N)), dan melacak jalur (menggunakan ruang ekstra - jadi, # 1 mungkin lebih unggul bahkan berpikir ruang mungkin diabaikan jika pohon biner seimbang dengan baik sehingga konsumsi memori tambahan akan tepat di O (log (N)).

   sehingga jalur dibandingkan (pada dasarnya mirip dengan jawaban yang diterima - tetapi jalur dihitung dengan mengasumsikan simpul penunjuk tidak ada dalam simpul pohon biner)

3. Hanya untuk penyelesaian ( tidak terkait dengan pertanyaan ), LCA di BST (O (log (N))

4. Tes

Rekursif:

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;
        }

di mana versi rekursif pribadi di atas dipanggil dengan metode publik berikut:

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;
        }

Solusi dengan melacak jalur kedua 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;
        }

di mana FindNodeAndPath didefinisikan sebagai

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) - tidak terkait (hanya untuk penyelesaian untuk referensi)

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;
        }

Tes Unit

[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);
            }
        }

Jika seseorang tertarik pada kode semu (untuk pekerjaan rumah di universitas) di sini adalah salah satunya.

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

Meskipun ini sudah dijawab, ini adalah pendekatan saya untuk masalah ini menggunakan bahasa pemrograman C. Meskipun kode menunjukkan pohon pencarian biner (sejauh memasukkan () yang bersangkutan), tetapi algoritma ini bekerja untuk pohon biner juga. Idenya adalah untuk membahas semua node yang terletak dari node A ke node B di inorder traversal, mencari indeks untuk ini di post order traversal. Node dengan indeks maksimum dalam post order traversal adalah leluhur umum terendah.

Ini adalah kode C yang berfungsi untuk mengimplementasikan fungsi untuk menemukan leluhur umum terendah dalam pohon biner. Saya menyediakan semua fungsi utilitas dll juga, tetapi lompat ke CommonAncestor () untuk pemahaman cepat.

#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);


}

Mungkin ada satu pendekatan lagi. Namun itu tidak seefisien yang sudah disarankan dalam jawaban.

• Buat vektor jalur untuk simpul n1.

• Buat vektor jalur kedua untuk simpul n2.

• Path vector menyiratkan set node dari yang akan dilintasi untuk mencapai node yang dimaksud.

• Bandingkan kedua vektor jalur. Indeks di mana mereka tidak cocok, mengembalikan simpul pada indeks itu - 1. Ini akan memberikan LCA.

Kontra untuk pendekatan ini:

Perlu melintasi pohon dua kali untuk menghitung vektor jalur. Perlu ruang O (h) tambahan untuk menyimpan vektor jalur.

Namun ini mudah diimplementasikan dan dipahami juga.

Kode untuk menghitung vektor jalur:

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;       
    }

Coba seperti ini

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;
}

Cara kasar:

• Di setiap simpul
  • X = temukan jika salah satu dari n1, n2 ada di sisi kiri Node
  • Y = temukan jika salah satu dari n1, n2 ada di sisi kanan Node
    • jika simpul itu sendiri adalah n1 || n2, kita dapat menyebutnya baik ditemukan di kiri atau kanan untuk keperluan generalisasi.
  • Jika X dan Y adalah benar, maka Node adalah CA

Masalah dengan metode di atas adalah bahwa kita akan melakukan "menemukan" beberapa kali, yaitu ada kemungkinan setiap node akan dilintasi beberapa kali. Kami dapat mengatasi masalah ini jika kami dapat merekam informasi sehingga tidak memprosesnya lagi (pikirkan pemrograman dinamis).

Jadi daripada melakukan menemukan setiap node, kami mencatat apa yang sudah ditemukan.

Cara yang lebih baik:

• Kami memeriksa untuk melihat apakah untuk node yang diberikan jika left_set (berarti n1 | n2 telah ditemukan di subtree kiri) atau right_set dalam mode first depth. (CATATAN: Kami memberikan root sendiri properti menjadi left_set jika salah satu dari keduanya adalah n1 | n2)
• Jika kedua left_set dan right_set maka node adalah LCA.

Kode:

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;
   }
}

Kode untuk Pencarian Pertama Luasnya untuk memastikan kedua node berada di pohon. Hanya kemudian bergerak maju dengan pencarian LCA. Berikan komentar jika Anda memiliki saran untuk ditingkatkan. Saya pikir kita mungkin dapat menandai mereka mengunjungi dan memulai kembali pencarian pada titik tertentu di mana kita tinggalkan untuk meningkatkan untuk simpul kedua (jika tidak ditemukan VISITED)

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;
}
}

Anda benar bahwa tanpa simpul orangtua, solusi dengan traversal akan memberi Anda O (n) kompleksitas waktu.

Pendekatan traversal Misalkan Anda menemukan LCA untuk node A dan B, pendekatan yang paling mudah adalah pertama-tama mendapatkan jalur dari root ke A dan kemudian mendapatkan jalur dari root ke B. Setelah Anda memiliki dua jalur ini, Anda dapat dengan mudah beralih di atasnya dan temukan simpul umum terakhir, yang merupakan leluhur bersama terendah dari A dan B.

Solusi rekursif Pendekatan lain adalah menggunakan rekursi. Pertama, kita bisa mendapatkan LCA dari pohon kiri dan pohon kanan (jika ada). Jika salah satu dari A atau B adalah simpul root, maka root adalah LCA dan kami hanya mengembalikan root, yang merupakan titik akhir rekursi. Saat kita terus membagi pohon menjadi sub-pohon, akhirnya, kita akan menekan A dan B.

Untuk menggabungkan solusi sub-masalah, jika LCA (pohon kiri) mengembalikan sebuah simpul, kita tahu bahwa A dan B berada di pohon kiri dan simpul yang dikembalikan adalah hasil akhir. Jika LCA (kiri) dan LCA (kanan) mengembalikan node yang tidak kosong, itu berarti A dan B masing-masing berada di pohon kiri dan kanan. Dalam hal ini, simpul akar adalah simpul umum terendah.

Periksa Leluhur Biasa Terendah untuk analisis dan solusi terperinci.

Beberapa solusi di sini mengasumsikan bahwa ada referensi ke simpul root, beberapa mengasumsikan bahwa tree adalah BST. Berbagi solusi saya menggunakan hashmap, tanpa referensi ke rootsimpul dan pohon bisa BST atau non-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
    }

Solusi 1: Rekursif - Lebih cepat

• Idenya adalah untuk melintasi pohon mulai dari root. Jika salah satu kunci yang diberikan p dan q cocok dengan root, maka root adalah LCA, dengan asumsi bahwa kedua kunci tersebut ada. Jika root tidak cocok dengan salah satu tombol, kami kembali untuk subtree kiri dan kanan.
• Node yang memiliki satu kunci hadir di subtree kirinya dan kunci lainnya hadir di subtree kanan adalah LCA. Jika kedua tombol terletak di subtree kiri, subtree kiri juga memiliki LCA, sebaliknya LCA terletak di subtree kanan.

• Kompleksitas Waktu: O (n)
• Kompleksitas Ruang: O (h) - untuk tumpukan panggilan rekursif

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)
    }
}

Solusi 2: Iteratif - Menggunakan pointer orangtua - Lebih lambat

• Buat tabel hash kosong.
• Masukkan p dan semua leluhurnya di tabel hash.
• Periksa apakah q atau leluhurnya ada dalam tabel hash, jika ya maka kembalikan leluhur pertama yang ada.

• Kompleksitas Waktu: O (n) - Dalam kasus terburuk kita mungkin mengunjungi semua simpul pohon biner.
• Kompleksitas Ruang: O (n) - Ruang yang digunakan pointer orangtua Hash-table, leluhur_set dan antrian, masing-masing akan menjadi 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;
    }
}