class Solution(object):
def lowestCommonAncestor(self, one, two):
"""
input: TreeNodeP one, TreeNodeP two
return: TreeNodeP
"""
# write your solution here
# this is the same as find intersection of two linked list
if not one and not two:
return None
ptr1 = one
len1 = 1
ptr2 = two
len2 = 1
while(ptr1 != None):
ptr1 = ptr1.parent
len1 += 1
while(ptr2 != None):
ptr2 = ptr2.parent
len2 += 1
# reset
ptr1 = one
ptr2 = two
if (len1 > len2):
# ptr one is longer
for i in range(len1-len2):
ptr1 = ptr1.parent
else :
for i in range(len2-len1):
ptr2 = ptr2.parent
while (ptr1 != ptr2):
ptr1 = ptr1.parent
ptr2 = ptr2.parent
return ptr1
Note to reset the pointers after measuring length
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.