使用Python使用父指针找到二叉树的最低公共祖先节点的程序
假设我们有一个二叉树和两个特定的节点x和y。我们必须找出二叉树中这两个节点的最低公共祖先节点。在二叉树中,最低公共祖先是两个节点x和y都是后代的最低节点。一个特定的节点也可以是自己的后代。我们需要找到该节点并将其作为输出返回。
树的节点结构如下 –
TreeNode:
data:<integer>
left:<TreeNode指针>
right:<TreeNode指针>
parent:<TreeNode指针>
在找到解决方案时,我们必须利用父指针。
因此,如果输入如下:
并且x = 3, y = 7,则输出将为5。
3和7都是5的后代,因此答案将是5。
为了解决这个问题,我们将按如下步骤进行 –
- path_p_r := 一个新的列表
-
当x不为null时,执行
- 在path_p_r的末尾插入x
-
x:=x的父节点
-
当y不为null时,执行
- 如果y存在于path_p_r中,则
- 返回y
- y:=y的父节点
- 如果y存在于path_p_r中,则
让我们看下面的实现以获得更好的理解 –
示例
class TreeNode:
def __init__(self, data, left = None, right = None, parent = None):
self.data = data
self.left = left
self.right = right
self.parent = parent
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data, parent=temp)
else:
temp.left = TreeNode(0,parent=temp)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data,parent=temp)
else:
temp.right = TreeNode(0,parent=temp)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def search_node(root, element):
if (root == None):
return None
if (root.data == element):
return root
res1 = search_node(root.left, element)
if res1:
return res1
res2 = search_node(root.right, element)
return res2
def solve(x, y):
path_p_r = []
while x:
path_p_r.append(x)
x = x.parent
while y:
if y in path_p_r:
return y
y = y.parent
root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(search_node(root, 3), search_node(root, 7)).data)
输入
[5, 3, 7, 2, 4, 1, 7, 6, 8, 10],3,7
输出
5