Interesting OJ profiler result


  • 0
    J

    At first I did a very naive approach where I recorded the individual paths down the tree then took the intersection of the paths. I submitted it and it beat 100% of the ruby solutions.

    def lowest_common_ancestor(root, p, q)
      path_p = []
      find(root,p,path_p)
      path_q = []
      find(root,q,path_q)
      (path_p & path_q).last
    end
    
    def find(root, elem, path)
      path << root.val
      if root.val == elem.val
        return root
      else
        if elem.val < root.val
          return find(root.left, elem, path)
        else
          return find(root.right, elem, path)
        end
      end
    end
    

    Then I read the discussion and realized there was a better approach so I changed to the following which only beats 16% of the ruby solutions.

    def lowest_common_ancestor(root, p, q)
      return root if root.nil?
      if p.val < root.val && q.val < root.val
        return lowest_common_ancestor(root.left, p, q)
      end
      if p.val > root.val && q.val > root.val
        return lowest_common_ancestor(root.right, p, q)
      end
      return root.val
    
    end
    

    Does anyone know why I would get that result?
    Thanks.


Log in to reply
 

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