Several methods java


  • 3
    S

    Simple one :
    use the properties of binary search tree

    1. val never duplicates

    2. left node val< father node val<right node val

      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if(root.val> p.val && root.val>q.val) return lowestCommonAncestor(root.left, p, q);
      if(root.val<p.val && root.val<q.val) return lowestCommonAncestor(root.right, p, q);
      return root;
      }

    One with any value(could say binary tree)

    1. write two more functions (find all the ancestors, check if the ancestor has this descendant or not)
      not good codes but solve two more issues(find all ancestor and check if ancestor has this descendant or not )

       public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if(p == root || q == root) return root;
       if(p == q || contains(p,q)) return p;// p is equal or upper level
       if(contains(q,p)) return q;	//q is upper level
       TreeNode temp = p;
       while(temp!= root){
           temp = findFather(root,p);
           if(contains(temp,q)) 
               return temp;
           else
               p=temp;
       }
       return null;
      

      }

      public boolean contains(TreeNode ancestor, TreeNode descendant){
      //ancestor contains descendant or not
      if(ancestor == null) return false;
      if(ancestor.left == null && ancestor.right == null) return false;
      if(ancestor.left == descendant || ancestor.right == descendant)
      return true;
      else
      return contains(ancestor.left, descendant) || contains(ancestor.right, descendant);
      }
      public TreeNode findFather(TreeNode root, TreeNode son){
      //return father node
      if(root == null) return null;
      if(root.left == null && root.right == null) return null;
      if(root.left == son || root.right == son) return root;
      if(findFather(root.left, son)!= null) return findFather(root.left, son);
      if (findFather(root.right,son)!=null) return findFather(root.right,son);
      return null;
      }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.