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

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告