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

更新于: 2020年10月12日

200 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告