Skip to content

Instantly share code, notes, and snippets.

@shamod
Created August 14, 2020 21:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save shamod/ec26497dbf4178d6255a9ff7ec4bb1f2 to your computer and use it in GitHub Desktop.
Save shamod/ec26497dbf4178d6255a9ff7ec4bb1f2 to your computer and use it in GitHub Desktop.
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
def findPath(root, x, res):
if not root: return False
res.append(root.val)
if root.val == x:
return True
if findPath(root.left, x, res) or findPath(root.right, x, res):
return True
res.pop()
return False
pres, qres = [],[]
curr = root
findPath(curr, p.val, pres)
curr = root
findPath(curr, q.val, qres)
pi, qi = 0, 0
while pi < len(pres) and qi < len(qres):
p_elem, q_elem = pres[pi], qres[qi]
if p_elem != q_elem:
break
pi += 1
qi += 1
return TreeNode(pres[pi - 1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment