用 Python 编写程序，用于查找二叉树中两个元素共同的祖先

pythonserver side programmingprogramming更新于 2026/1/24 15:08:17

假设我们有一棵二叉树，还有两个数字 a 和 b，我们必须找到以 a 和 b 作为后代的最低节点的值。我们必须记住，一个节点可以是它自己的后代。

因此，如果输入如下

a = 6，b = 2，则输出为 4

要解决这个问题，我们将遵循以下步骤 −

定义一个方法solve()，它将获取root和a，b
如果root为空，则
- 返回-1
如果root的值是a或b，则
- 返回根的值
left := resolve(根的左边，a，b)
right := resolve(根的右边，a，b)
如果左边或右边不为 -1，则
- 返回根的值
如果左边不等于 -1，则返回左边，否则返回右边
从主方法调用solve(root)

让我们看看下面的实现以便更好地理解 −

示例

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