Burada İkili Ağaç mutlaka İkili bir Arama Ağacı olmayabilir.
Yapı olarak almış olabilir

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

Bir arkadaşla çalışabilirim maksimum çözüm bu tür bir şey oldu
Düşünün this binary tree :

Geçişi verir - 8, 4, 9, 2, 5, 1, 6, 3, 7 O'na

Ve geçişi verir - 8, 9, 4, 5, 2, 6, 7, 3, 1 postorder

Yani örneğin, bulmak istiyorsan, bu ortak ata düğümleri 8 ve 5, sonra yaparız bir liste tüm düğüm noktaları arasında 8 ve 5'te O'na ağaç geçişi, ki bu durumda olmak [4, 9, 2]. O zaman 2 olan son postorder Çapraz geçiş görünen kontrol ediyoruz. 8 ve 5 dolayısıyla ortak atası 2.

Karmaşıklığı için bu algoritma, inanıyorum O(n) (O(n) için O'na/postorder dolaşımları, geri kalan adımları tekrar O(n) beri onlar hiçbir şey daha basit tekrar dizileri). Ama bunun yanlış olduğunu güçlü bir şans var. :-)

Ama bu çok kaba bir yaklaşım olur, ve eğer bir olay çıkarsa emin değilim. Bu sorun için (muhtemelen daha fazla) uygun başka bir çözüm var mı?

Eğer doğrudan kendi çocuğu gibi ya p q herhangi bir düğüm bulursanız root düğüm ve aşağı doğru hareket başlayarak sonra LCA.

Eğer başka bir(veya sağ) sol alt(veya sol) sağ alt ağacı ve q p ile bir düğüm daha sonra bulursanız, LCA.

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

Yukarıdaki kod ya da diğer doğrudan çocuk başarısız. Aşağıdaki düzeltmeleri:

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

Code In Action