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

使用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)

输入

[5, 3, 7, 2, 4, 1, 7, 6, 8, 10],3,7

输出

5

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程