首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在Tree[Binary]中找到最低公共祖先,但在python中有多个节点?

在Tree[Binary]中找到最低公共祖先,但在Python中有多个节点。

在二叉树中,最低公共祖先(Lowest Common Ancestor,LCA)是指两个节点的最近共同祖先节点。当在Python中有多个节点时,我们需要找到这些节点的最低公共祖先。

解决这个问题的一种常见方法是使用递归。我们可以从根节点开始,递归地遍历整个二叉树,直到找到目标节点或遍历到叶子节点。对于每个遍历到的节点,我们可以检查其左右子树是否包含目标节点。如果左右子树都包含目标节点,那么当前节点就是最低公共祖先。如果只有一侧包含目标节点,那么最低公共祖先必定在包含目标节点的一侧。我们可以继续递归地在该子树中寻找最低公共祖先。

以下是一个示例代码:

代码语言:txt
复制
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findLowestCommonAncestor(root, p, q):
    if root is None or root == p or root == q:
        return root
    
    left = findLowestCommonAncestor(root.left, p, q)
    right = findLowestCommonAncestor(root.right, p, q)
    
    if left and right:
        return root
    elif left:
        return left
    else:
        return right

# 创建一个二叉树
#       3
#      / \
#     5   1
#    / \ / \
#   6  2 0  8
#     / \
#    7   4
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

p = root.left  # 节点5
q = root.left.right.right  # 节点4

lca = findLowestCommonAncestor(root, p, q)
print("最低公共祖先节点的值为:", lca.val)

这段代码中,我们首先定义了一个TreeNode类来表示二叉树的节点。然后,我们使用递归函数findLowestCommonAncestor来找到最低公共祖先节点。在示例中,我们创建了一个二叉树,并找到节点5和节点4的最低公共祖先节点。最后,我们打印出最低公共祖先节点的值。

对于这个问题,腾讯云没有特定的产品或服务与之直接相关。然而,腾讯云提供了强大的云计算基础设施和服务,可以支持开发人员构建和部署各种应用程序,包括涉及树结构的算法和问题。您可以参考腾讯云的官方文档和产品介绍来了解更多关于腾讯云的信息。

参考链接:

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

Leetcode 236. Lowest Common Ancestor of a Binary Tree

根据LCA的定义,二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点,LCA的定义没什么好解释的,主要是这道题的解法。   我们要找p和q的最小公共节点,我开始想到的方法是先找出root分别到p和q的路径,既然路径都知道了,就从两条路径的末尾倒着往前来,第一个共同节点就是LCA,但其实有更简单易懂的方法。   对于任意一个p和q的祖先节点node,都有三种情况,情况一:p和q的LCA在node的左子树,情况二:p和q的LCA在node的右子树,情况三:node就是p和q的LCA。   说到递归,肯定是有边界条件的,这里的边界条件除了递归到叶子节点外,还有就是到达p或q,因为你p或者q的子孙节点不可能是p和q的LCA。在代码实现过程中,如果没到递归边界,我们先从左子树找LCA,比如找到了liftLCA。再从从右子树找LCA,比如找到了rightLCA。   这里有几种情况:(1). liftLCA和rightLCA都不为空,肯定liftLCA和rightLCA分别是p和q,所以当然root节点肯定是LCA。(2).liftLCA和rightLCA其中之一为空,可能是在左子树或者又子树中找到了LCA,直接返回非空的一个。(3).liftLCA和rightLCA其中之一为空,还有可能是当前root节点的左右子树只包含p或q节点其中之一,这种情况递归回溯到上层是就会最终变成情况(1)或(2)。   我的解题代码如下(Run Time:12ms)

01
领券