在Tree[Binary]中找到最低公共祖先，但在python中有多个节点？

Question

要找到树的最低祖先，请尝试下面的代码。

# A binary tree node 
class Node: 
    # Constructor to create a new binary node 
    def __init__(self, key): 
        self.key =  key 
        self.left = None
        self.right = None

# Finds the path from root node to given root of the tree. 
# Stores the path in a list path[], returns true if path  
# exists otherwise false 
def findPath( root, path, k): 

    # Baes Case 
    if root is None: 
        return False

    # Store this node is path vector. The node will be 
    # removed if not in path from root to k 
    path.append(root.key) 

    # See if the k is same as root's key 
    if root.key == k : 
        return True

    # Check if k is found in left or right sub-tree 
    if ((root.left != None and findPath(root.left, path, k)) or
            (root.right!= None and findPath(root.right, path, k))): 
        return True 

    # If not present in subtree rooted with root, remove 
    # root from path and return False 

    path.pop() 
    return False

# Returns LCA if node n1 , n2 are present in the given 
# binary tre otherwise return -1 
def findLCA(root, n1, n2): 

    # To store paths to n1 and n2 fromthe root 
    path1 = [] 
    path2 = [] 

    # Find paths from root to n1 and root to n2. 
    # If either n1 or n2 is not present , return -1  
    if (not findPath(root, path1, n1) or not findPath(root, path2, n2)): 
        return -1 

    # Compare the paths to get the first different value 
    i = 0 
    while(i < len(path1) and i < len(path2)): 
        if path1[i] != path2[i]: 
            break
        i += 1
    return path1[i-1] 


root = Node(0) 
root.left = Node(1) 
root.right = Node(2) 
root.left.left = Node(3) 
root.left.right = Node(4)
root.right.left = Node(5) 
root.right.right = Node(6) 
root.right.right = Node(11) 
root.left.right.left = Node(7)
root.left.right.right = Node(8)
root.right.left.left = Node(9) 
root.right.left.left.left = Node(10) 


print "LCA(3, 8) = %d" %(findLCA(root, 3, 8,)) 
print "LCA(1, 8) = %d" %(findLCA(root, 1, 8)) 
print "LCA(8, 6) = %d" %(findLCA(root,8,6)) 
print "LCA(10, 2) = %d" %(findLCA(root,10, 2)) 
print "LCA(7, 6) = %d" %(findLCA(root,7, 6)) 
print "LCA(0, 9) = %d" %(findLCA(root,0, 9)) 
print "LCA(10, 11) = %d" %(findLCA(root,10,11)) 
print "LCA(11, 3) = %d" %(findLCA(root,11,3)) 

但是有一种情况，在中有多个节点连接到同一个节点，在这种情况下，程序会出错，这是有意义的，因为左边，右边的节点。

​

​

OUtput:
LCA(3, 8) = 1
LCA(1, 8) = 1
LCA(8, 6) = -1
LCA(10, 2) = 2
LCA(7, 6) = -1
LCA(0, 9) = 0
LCA(10, 11) = 2
LCA(11, 3) = 0

有什么方法可以克服多个节点连接到同一个节点的问题吗？请提供您的意见。

Answer 1

尝试使用下面的方法。它所做的是，它将继续递归地遍历树，直到节点的路径分离。并返回节点本身。

def lca(root, v1, v2):
if (v1>root.info) and (v2>root.info):
    res = lca(root.right,v1,v2)
elif (v1<root.info) and (v2<root.info):
    res = lca(root.left,v1,v2)
else:
    res = root
return res