Advertisement
rishu110067

Untitled

Jan 25th, 2022
881
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     /*
  2.     Node structure
  3.     class Node{
  4.         public Node left,right; // for left and the right child !!
  5.         public int data;
  6.     }
  7.  
  8.     */
  9.     int lca(Node root, Node a, Node b){
  10.        
  11.         if(a == b) return a.data;
  12.        
  13.         Node ancestor = null;
  14.        
  15.         GetLowestCommonAncestorHelper(root, a, b, ref ancestor);
  16.        
  17.         if(ancestor == null) return -1;
  18.        
  19.         return ancestor.data;
  20.     }
  21.    
  22.      TreeInfo GetLowestCommonAncestorHelper(Node node, Node p, Node q, ref Node ancestor) {
  23.         if(node == null) return new TreeInfo(false, 0);
  24.        
  25.         var leftInfo = GetLowestCommonAncestorHelper(node.left, p, q, ref ancestor);
  26.         var righInfo = GetLowestCommonAncestorHelper(node.right, p, q, ref ancestor);
  27.        
  28.         var treeInfo =  new TreeInfo(false, 0);
  29.        
  30.         if(leftInfo.isAncestor && righInfo.isAncestor)
  31.         {
  32.             if(leftInfo.count == 2) return leftInfo;
  33.            
  34.             else if(righInfo.count == 2) return righInfo;
  35.            
  36.             treeInfo.isAncestor = true;
  37.             treeInfo.count = 2;
  38.             ancestor = node;
  39.             return treeInfo;
  40.         }
  41.         else
  42.         {
  43.             if(node == p || node == q)
  44.             {
  45.                 treeInfo.isAncestor = true;
  46.                 treeInfo.count = 1;
  47.             }
  48.            
  49.             if(leftInfo.isAncestor || righInfo.isAncestor)
  50.             {
  51.                 treeInfo.isAncestor = true;
  52.                 treeInfo.count += 1;
  53.             }
  54.            
  55.             if(treeInfo.count == 2) ancestor = node;
  56.         }
  57.        
  58.         return treeInfo;
  59.     }
  60.    
  61.     class TreeInfo{
  62.         public bool isAncestor = false;
  63.         public int count;
  64.         public TreeInfo(bool isAncestor, int count){this.isAncestor = isAncestor; this.count = count;}
  65.     }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement