python - 在树中查找最低共同祖先 [二进制] 但在 python 中有多个节点?
问题描述
要查找树的最低祖先,请尝试以下代码。
# 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
我可以通过多个节点克服同一个节点的任何方式吗?请提供您的意见。
解决方案
尝试使用以下方法。它所做的是,它将继续递归遍历树,直到节点的路径分开。它返回节点本身。
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
推荐阅读
- c++ - 重载的 ++ 运算符仅适用于左侧(C++)
- postgresql - 使用 jpa 和 spring boot 为 postgreSQL 生成 uuid4
- django - 如何在 django 中使用 api 创建(POST)请求
- python - 熊猫数据框按组和日期计算重复次数
- javascript - 我如何知道 Trustpilot Embeded 上的数据是空的?
- flutter - 如何获得下图中给出的边界半径。#扑
- spring-boot - 是否有可能在 Spring 中使用环境变量选择身份验证?
- php - 如何在jquery ajax成功中获取多个值参数?
- python - 将参数传递给 pytest.lazy_fixture
- ios - ARKit 无法识别参考图像