algorithm - सहन - मानवाचा इतिहास




किसी भी बाइनरी पेड़ में दो नोड्स के सबसे कम आम पूर्वज कैसे खोजें? (20)

अगर कोई छद्म कोड (विश्वविद्यालय के घर के काम के लिए) में रूचि रखता है तो यहां एक है।

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

यहां बाइनरी ट्री एक बाइनरी सर्च ट्री नहीं हो सकती है।
संरचना के रूप में लिया जा सकता है -

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

एक दोस्त के साथ काम करने का अधिकतम समाधान इस तरह का था -
इस बाइनरी पेड़ पर विचार करें :

बाइनरी ट्री http://lcm.csa.iisc.ernet.in/dsa/img151.gif

इनऑर्डर ट्रैवर्सल उपज - 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 है।

इस एल्गोरिदम के लिए जटिलता, मेरा मानना ​​है कि ओ (एन) (ओ (एन) इनऑर्डर / पोस्टऑर्डर ट्रैवर्सल के लिए है, बाकी के कदम फिर से ओ (एन) हैं क्योंकि वे सरणी में सरल पुनरावृत्तियों से ज्यादा कुछ नहीं हैं)। लेकिन एक मजबूत मौका है कि यह गलत है। :-)

लेकिन यह एक बहुत ही कच्चा दृष्टिकोण है, और मुझे यकीन नहीं है कि यह कुछ मामलों के लिए टूट जाता है। क्या इस समस्या के लिए कोई अन्य (संभवतः अधिक इष्टतम) समाधान है?


इस पेड़ पर विचार करें

अगर हम पोस्टऑर्डर और प्रीऑर्डर ट्रैवर्सल करते हैं और पहले सामान्य आम पूर्ववर्ती और उत्तराधिकारी को पाते हैं, तो हमें आम पूर्वज मिल जाता है।

पोस्टर = = 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 के सबसे आम पूर्वजों

पोस्टऑर्डर में हमारे पास = 8,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 उत्तर है


उदाहरण के लिए, अब तक दिए गए उत्तर रिकर्सन या स्टोर का उपयोग करते हैं, उदाहरण के लिए, स्मृति में पथ।

यदि आपके पास बहुत गहरा पेड़ है तो इन दोनों दृष्टिकोण विफल हो सकते हैं।

इस सवाल पर मेरा लेना है। जब हम दोनों नोड्स की गहराई (रूट से दूरी) की जांच करते हैं, यदि वे बराबर हैं, तो हम सुरक्षित पूर्वजों की ओर दोनों नोड्स से सुरक्षित रूप से आगे बढ़ सकते हैं। यदि गहराई में से एक बड़ा है तो हमें दूसरे में रहने के दौरान गहरे नोड से आगे बढ़ना चाहिए।

यहां कोड है:

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;    

इस एल्गोरिदम की समय जटिलता है: ओ (एन)। इस एल्गोरिदम की अंतरिक्ष जटिलता है: ओ (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;

एक संतुलित बाइनरी पेड़ के लिए नीचे रिकर्सिव एल्गोरिदम ओ (लॉग एन) में चलाएगा। यदि getLCA () फ़ंक्शन में पास किए गए नोड्स में से कोई भी रूट के समान होता है तो रूट एलसीए होगा और कोई भी पुनरावृत्ति करने की आवश्यकता नहीं होगी।

परीक्षण के मामलों। [1] दोनों नोड्स एन 1 और एन 2 पेड़ में हैं और उनके माता-पिता नोड के दोनों तरफ रहते हैं। [2] या तो नोड एन 1 या एन 2 रूट है, एलसीए रूट है। [3] केवल एन 1 या एन 2 पेड़ में है, एलसीए या तो पेड़ की जड़ के बाएं उपट्री का रूट नोड होगा, या एलसीए पेड़ की जड़ के दाहिने उप-रूट का रूट नोड होगा।

[4] न तो एन 1 या एन 2 पेड़ में है, कोई एलसीए नहीं है। [5] एन 1 और एन 2 दोनों एक दूसरे के बगल में एक सीधी रेखा में हैं, एलसीए या तो एन 1 या एन 2 होगा जो कभी पेड़ की जड़ से बंद हो जाता है।

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

जावा में कामकाजी कोड यहां है

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

दो नोड के सामान्य पूर्वजों को खोजने के लिए: -

  • बाइनरी खोज का उपयोग करके पेड़ में दिए गए नोड नोड 1 को ढूंढें और एरे में इस प्रक्रिया में देखे गए सभी नोड्स को ए 1 कहें। समय - ओ (लॉग इन), स्पेस - ओ (लॉग इन)
  • बाइनरी खोज का उपयोग करके पेड़ में दिए गए नोड 2 को ढूंढें और एक सरणी में इस प्रक्रिया में देखे गए सभी नोड्स को ए 2 कहते हैं। समय - ओ (लॉग इन), स्पेस - ओ (लॉग इन)
  • यदि ए 1 सूची या ए 2 सूची खाली है तो एक नोड मौजूद नहीं है इसलिए कोई आम पूर्वज नहीं है।
  • यदि ए 1 सूची और ए 2 सूची गैर-खाली हैं तो सूची में तब तक देखें जब तक आपको गैर-मिलान नोड मिल जाए। जैसे ही आपको ऐसा नोड मिलता है, उसके बाद नोड सामान्य पूर्वज होता है।

यह बाइनरी खोज पेड़ के लिए काम करेगा।


बस पूरे पेड़ की root से नीचे चले जाओ, जब तक कि दोनों नोड्स न हों, p और q कहें, जिसके लिए पूर्वजों को पाया जाना चाहिए, एक ही उप-पेड़ में हैं (जिसका अर्थ है कि उनके मूल्य दोनों छोटे या दोनों रूट की तुलना में बड़े हैं)।

यह जड़ से सीधे आम पूर्व पूर्वज तक चलता है, बाकी पेड़ को नहीं देखता है, इसलिए यह जितना तेज़ हो जाता है उतना तेज़ होता है। ऐसा करने के कुछ तरीके।

Iterative, ओ (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 - (लंबा) p.val) * (root.val - (लंबा) 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);
}

मुझे एक समाधान मिला

  1. अंदरूनी ले लो
  2. प्रीऑर्डर लें
  3. पोस्टऑर्डर लें

3 ट्रैवर्सल के आधार पर, आप तय कर सकते हैं कि एलसीए कौन है। एलसीए से दोनों नोड्स की दूरी मिलती है। इन दो दूरी जोड़ें, जो जवाब है।



यदि यह नोड एक्स के बच्चों के साथ 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. एक्स और वाई का प्रतिनिधित्व करने के लिए आवश्यक बिट्स प्राप्त करें जो बाइनरी खोज का उपयोग कर रहे हैं ओ (लॉग (32))
  2. एक्स और वाई के बाइनरी नोटेशन का सामान्य उपसर्ग आम पूर्वज है
  3. जो भी बड़ी संख्या में बिट्स द्वारा दर्शाया जाता है उसे के >> diff द्वारा लाया जाता है
  4. k = x ^ y erazes x और y के सामान्य उपसर्ग को मिटा देता है
  5. शेष प्रत्यय का प्रतिनिधित्व बिट्स पाएं
  6. सामान्य उपसर्ग प्राप्त करने के लिए प्रत्यय बिट्स द्वारा एक्स या वाई को शिफ्ट करें।

यह काम करता है क्योंकि मूल रूप से बड़ी संख्या को दो बार दोहराया जाता है जब तक कि दोनों संख्या बराबर न हों। वह संख्या आम पूर्वज है। विभाजन प्रभावी ढंग से सही शिफ्ट opearation है। तो हमें निकटतम पूर्वजों को खोजने के लिए दो संख्याओं के सामान्य उपसर्ग को खोजने की आवश्यकता है


यह यहां पाया जा सकता है: - 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;
        }
    }
}

संदर्भ के लिए यहां सी # (.net) (ऊपर चर्चा दोनों) में दो दृष्टिकोण हैं:

  1. बाइनरी पेड़ (ओ (एन) में एलसीए खोजने का रिकर्सिव संस्करण - जैसा कि प्रत्येक नोड में सबसे अधिक देखा जाता है) (समाधान का मुख्य बिंदु एलसीए (ए) केवल बाइनरी पेड़ में नोड है जहां दोनों तत्व subtrees के दोनों तरफ रहते हैं (बाएं और दाएं) एलसीए है। (बी) और इससे कोई फर्क नहीं पड़ता कि कौन सा नोड मौजूद है - शुरुआत में मैंने उस जानकारी को रखने की कोशिश की, और जाहिर है कि रिकर्सिव फ़ंक्शन इतना भ्रमित हो गया। एक बार मुझे एहसास हुआ, यह बहुत ही सुरुचिपूर्ण हो गया।

  2. दोनों नोड्स (ओ (एन) खोजना, और पथों का ट्रैक रखना (अतिरिक्त स्थान का उपयोग करना - इसलिए, # 1 शायद बेहतर है, यह भी सोचा जाता है कि यदि संभवतः बाइनरी पेड़ अच्छी तरह से संतुलित है तो स्पेस शायद नगण्य है क्योंकि अतिरिक्त मेमोरी खपत केवल हे (लॉग (एन))।

    ताकि पथ की तुलना की जा सके (संक्षेप में स्वीकार्य उत्तर के समान - लेकिन पथों की गणना करके गणना की जाती है कि बाइनरी पेड़ नोड में पॉइंटर नोड मौजूद नहीं है)

  3. बस पूरा होने के लिए ( प्रश्न से संबंधित नहीं ), बीएसटी में एलसीए (ओ (लॉग (एन))

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

बीएसटी (एलसीए) - संबंधित नहीं है (केवल संदर्भ के लिए पूरा होने के लिए)

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

स्कैला में, कोड है:

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


Code for A Breadth First Search to make sure both nodes are in the tree. Only then move forward with the LCA search. Please comment if you have any suggestions to improve. I think we can probably mark them visited and restart the search at a certain point where we left off to improve for the second node (if it isn't found 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;
}
}

Crude way:

  • At every node
    • X = find if either of the n1, n2 exist on the left side of the Node
    • Y = find if either of the n1, n2 exist on the right side of the Node
      • if the node itself is n1 || n2, we can call it either found on left or right for the purposes of generalization.
    • If both X and Y is true, then the Node is the CA

The problem with the method above is that we will be doing the "find" multiple times, ie there is a possibility of each node getting traversed multiple times. We can overcome this problem if we can record the information so as to not process it again (think dynamic programming).

So rather than doing find every node, we keep a record of as to whats already been found.

Better Way:

  • We check to see if for a given node if left_set (meaning either n1 | n2 has been found in the left subtree) or right_set in a depth first fashion. (NOTE: We are giving the root itself the property of being left_set if it is either n1 | n2)
  • If both left_set and right_set then the node is a 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;
   }
}

There can be one more approach. However it is not as efficient as the one already suggested in answers.

  • Create a path vector for the node n1.

  • Create a second path vector for the node n2.

  • Path vector implying the set nodes from that one would traverse to reach the node in question.

  • Compare both path vectors. The index where they mismatch, return the node at that index - 1. This would give the LCA.

Cons for this approach:

Need to traverse the tree twice for calculating the path vectors. Need addtional O(h) space to store path vectors.

However this is easy to implement and understand as well.

Code for calculating the path vector:

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

Try like this

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

PHP में कोड। मैंने माना है कि पेड़ एक ऐरे बाइनरी पेड़ है। इसलिए, आपको एलसीए की गणना करने के लिए पेड़ की भी आवश्यकता नहीं है। इनपुट: दो नोड्स आउटपुट की अनुक्रमणिका: एलसीए की अनुक्रमणिका

    <?php
 global $Ps;

function parents($l,$Ps)
{

    if($l % 2 ==0)
        $p = ($l-2)/2;
    else            
        $p = ($l-1)/2;

    array_push($Ps,$p);     
    if($p !=0)
        parents($p,$Ps);

    return $Ps; 
}
function lca($n,$m)
{
    $LCA = 0;
    $arr1 = array();
    $arr2 = array();
    unset($Ps); 
$Ps = array_fill(0,1,0);
    $arr1 = parents($n,$arr1);
    unset($Ps); 
$Ps = array_fill(0,1,0);
    $arr2 = parents($m,$arr2);

    if(count($arr1) > count($arr2))
        $limit = count($arr2);
    else
        $limit = count($arr1);

    for($i =0;$i<$limit;$i++)
    {
        if($arr1[$i] == $arr2[$i])
        {
            $LCA = $arr1[$i];
            break;
        }
    }
    return $LCA;//this is the index of the element in the tree

}

var_dump(lca(5,6));
?>

मुझे बताओ कि क्या कोई कमी है।


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
}






least-common-ancestor