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

假设我们给定一个二叉树，并要求找出树中所有节点的最近公共祖先。二叉树中的最近公共祖先是最底层的节点，节点x1、x2、x3……xn都是其后代。某个特定节点也可以是其自身的后代。我们必须找到该节点并将其作为输出返回。输入是树的根节点以及我们必须找到其祖先的节点列表。

因此，如果输入类似于

并且我们必须找到其祖先的节点列表为[6, 8]；则输出将为7。

输出为7，因为节点6和8的最底层祖先节点是7。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数fn()。这将接收节点作为参数

    • 如果节点类似于空，则

      • 返回节点

    • 否则，当节点存在于nodes中时，则

      • 返回节点

    • left := fn(节点的左子节点),

    • right := fn(节点的右子节点)

    • 如果left和right都不为空，则

      • 返回节点

    • 否则，

      • 如果left或right不为空，则

        • 返回节点

  • nodes := 一个新的列表

  • 对于node_list中的每个元素，执行

    • 将search_node(root, elem)插入到nodes的末尾

  • nodes := 从nodes创建的新集合

  • 返回fn(root)

让我们看看下面的实现来更好地理解：

示例

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

更新于：2021年5月29日

浏览量：138

开启您的职业生涯

完成课程获得认证

开始学习
广告