使用Python使用父指针找到二叉树的最低公共祖先节点的程序

假设我们有一个二叉树和两个特定的节点x和y。我们必须找出二叉树中这两个节点的最低公共祖先节点。在二叉树中，最低公共祖先是两个节点x和y都是后代的最低节点。一个特定的节点也可以是自己的后代。我们需要找到该节点并将其作为输出返回。

树的节点结构如下 –

TreeNode：
   data：＜integer＞
   left：＜TreeNode指针＞
   right：＜TreeNode指针＞
   parent：＜TreeNode指针＞

在找到解决方案时，我们必须利用父指针。

因此，如果输入如下：

使用Python使用父指针找到二叉树的最低公共祖先节点的程序

并且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的父节点

让我们看下面的实现以获得更好的理解 –

示例

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)