使用Python找出给定节点二叉树最低公共祖先的程序

假设我们有一个二叉树，要求找出树中所有节点的最低公共祖先。二叉树中的最低公共祖先是节点x1，x2，x3，……，xn的最低祖先节点。一个特定的节点也可能是它本身的后代。我们必须找到该节点并将其作为输出返回。输入是树的根节点和我们要找到祖先的节点列表。

因此，如果输入是

和要找到祖先的节点列表是[6，8]，则输出将为7。

输出为7，因为节点6和8均是7的后代节点。

为解决此问题，我们将按照以下步骤执行 –

• 定义一个函数fn()，这将接受节点。
  • 如果节点类似于null，则
    • 返回节点
  • 否则当节点存在于节点列表中时，则
    • 返回节点
  • left：= fn(node的左子树)，

  • right：= fn(node的右子树)

  • 如果left和right不为null，则

    • 返回节点
  • 否则，
    • 如果left或right不为null，则

    • 返回节点

• nodes：=新列表

• 对于node_list中的每个elem，执行以下操作

  • 将search_node(root，elem)插入到nodes的末尾
• nodes：=新节点集从nodes

• 返回fn(root)

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

更多Python相关文章，请阅读：Python 教程

示例

import collections
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
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)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         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 print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
def solve(root, node_list):
   nodes = []
   for elem in node_list:
      nodes.append(search_node(root, elem))
      nodes = set(nodes)
def fn(node):
   if not node:
      return node
   elif node in nodes:
      return node
      left, right = fn(node.left), fn(node.right)
      return node if left and right else left or right
   return fn(root)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, [6,8]).data)

输入

make_tree([5, 3, 7, 2, 4, 6, 8]), [6, 8]

输出

7