Python程式：查詢二叉樹中兩個元素的共同祖先

假設我們有一棵二叉樹，我們還有兩個數字a和b，我們需要找到具有a和b作為後代的最低節點的值。我們需要記住，一個節點可以是它自己的後代。

因此，如果輸入類似於

a = 6，b = 2，則輸出將為4

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

• 定義一個方法solve()，它將接收根節點以及a和b

• 如果根節點為空，則

  • 返回-1

• 如果根節點的值是a或b，則

  • 返回根節點的值

• left := solve(根節點的左子節點, a, b)

• right := solve(根節點的右子節點, a, b)

• 如果left或right不為-1，則

  • 返回根節點的值

• 如果left不等於-1，則返回left，否則返回right

• 從主方法呼叫solve(根節點)

讓我們看看以下實現以獲得更好的理解 -

示例

 線上演示

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

class Solution:
   def solve(self, root, a, b):
      if not root:
         return -1
      if root.val in (a, b):
         return root.val
      left = self.solve(root.left, a, b)
      right = self.solve(root.right, a, b)
      if -1 not in (left, right):
         return root.val
      return left if left != -1 else right
ob = Solution()
root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root, 6, 2))

輸入

root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
6, 2

輸出

4

Arnab Chakraborty

更新於: 2020年10月12日

200 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始