Created
October 9, 2015 16:48
-
-
Save dusan87/abe4594601f5c4dcc95b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
I use logic that use just node values, which is a bit simpler | |
""" | |
class Node(object): | |
def __init__(self, value, parentNode): | |
self.value = value | |
self.parent = parentNode | |
def node_ancesors(node): | |
ancesors = [node.value, ] | |
while node.parent: | |
ancesors.append(node.value) | |
node = node.parent | |
return ancesors | |
def lca(node1, node2): | |
ancs1 = node_ancesors(node1) | |
ancs2 = node_ancesors(node2) | |
closest = max(set(ancs1) & set(ancs2)) | |
print closest | |
def improved_lca(node1, node2): | |
if node1.value == node2.value: | |
return node1.value | |
if not node1.parent: | |
return node1.value | |
if not node2.parent: | |
return node1.value | |
if node1.parent.value == node2.parent.value: | |
return node1.parent.value | |
return lca(node1, node2) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment