LCA(Lowest Common Ancestor)是指二叉树中两个结点的最近公共祖先。要找到二叉树中所有结点对的LCA,可以使用深度优先搜索(DFS)的方法。
具体步骤如下:
findLCA(root, node1, node2)
,其中root
表示二叉树的根节点,node1
和node2
表示要找LCA的两个结点。root
是否为空或等于node1
或node2
,如果是,则返回root
。findLCA
函数,分别传入root
的左子树和右子树,得到两个返回值left
和right
。left
和right
都不为空,说明node1
和node2
分别位于root
的左右子树中,那么root
就是它们的LCA,直接返回root
。left
为空,说明node1
和node2
都不在root
的左子树中,那么它们的LCA一定在root
的右子树中,返回right
。right
为空,说明node1
和node2
都不在root
的右子树中,那么它们的LCA一定在root
的左子树中,返回left
。下面是一个示例代码:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findLCA(root, node1, node2):
if not root or root == node1 or root == node2:
return root
left = findLCA(root.left, node1, node2)
right = findLCA(root.right, node1, node2)
if left and right:
return root
elif left:
return left
else:
return right
这样,调用findLCA
函数,传入二叉树的根节点和要找LCA的两个结点,即可得到它们的LCA。
关于腾讯云相关产品和产品介绍链接地址,由于要求不能提及具体品牌商,建议在腾讯云官方网站上查找相关产品,例如腾讯云的云服务器、云数据库、云存储等产品,以满足具体应用场景的需求。
领取专属 10元无门槛券
手把手带您无忧上云