使用Python查詢二叉樹的最低公共祖先的程式

假設我們給定一棵二叉樹以及兩個特定的節點x和y。我們必須從二叉樹中找出這兩個節點的最低公共祖先。二叉樹中最低的公共祖先是指x和y節點都是其後代的最低節點。此外，特定節點也可以是其自身的後代。我們必須找到該節點並將其作為輸出返回。

因此，如果輸入類似於

並且x = 2，y = 4；則輸出將為3。

節點2和4的後代節點是3。因此，將返回3。

為了解決這個問題，我們將遵循以下步驟：

• 定義一個函式dfs()。這將接收節點作為引數。

  • 如果節點類似於null，則

    • 返回

  • 如果節點存在於列表[x,y]中，則

    • left := dfs(節點的左子節點)

    • right := dfs(節點的右子節點)

    • 如果left或right非零，則

      • ans := 節點

      • 返回節點

  • left := dfs(節點的左子節點)

  • right := dfs(節點的右子節點)

  • 如果left和right均不為null，則

    • ans := 節點

    • 返回節點

  • 返回left或right

• ans := dfs(根節點)

• 返回ans

示例

 線上演示

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 solve(root, x, y):
def dfs(node):
   if not node:
      return
   if node in [x,y]:
      left = dfs(node.left)
      right = dfs(node.right)
   if left or right:
      ans = node
      return node
      left = dfs(node.left)
      right = dfs(node.right)
   if left and right:
      ans = node
      return node
      return left or right
      ans = dfs(root)
   return ans
root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(root, search_node(root, 2), search_node(root, 4)).data)

輸入

make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10]),
search_node(root, 2),
search_node(root, 4)

輸出

3

Arnab Chakraborty

更新於：2021年5月28日

117 次瀏覽

啟動您的職業生涯

完成課程後獲得認證

開始