难度: Medium
设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。
运行时间: 38 ms
内存: 20.4 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
def dfs(node, p, q):
if not node:
return None
if node.val == p.val or node.val == q.val:
return node
left = dfs(node.left, p, q)
right = dfs(node.right, p, q)
if left and right:
return node
return left or right
return dfs(root, p, q)
这个题解使用了递归的深度优先搜索（DFS）策略来寻找二叉树中两个节点的最低公共祖先。递归函数检查当前节点是否为null，如果是，则返回null。如果当前节点是p或q中的一个，则返回当前节点，表示找到了其中一个节点。然后，递归地在左右子树中查找p和q。如果在左子树中找到了p或q，并且在右子树中也找到了，那么当前节点就是p和q的最低公共祖先。如果只在左子树或右子树中找到了p或q，那么返回相应的非null结果。这个方法利用了二叉树的性质，通过递归来简化查找过程。
时间复杂度: O(n)
空间复杂度: O(h)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
# DFS function to find lowest common ancestor
def dfs(node, p, q):
# Base case: if current node is null
if not node:
return None
# If current node is either p or q
if node.val == p.val or node.val == q.val:
return node
# Recurse on left and right child
left = dfs(node.left, p, q)
right = dfs(node.right, p, q)
# If both sides returned non-null, current node is the LCA
if left and right:
return node
# Otherwise, return the non-null side
return left or right
# Start DFS from the root
return dfs(root, p, q)
在这种情况下，由于递归函数`dfs`会在没有找到p或q的情况下返回`None`，最终的结果将是`None`。这是因为每次递归调用都不会找到p或q，导致所有递归调用都返回`None`，最终`lowestCommonAncestor`函数也将返回`None`。
如果p是q的祖先，那么在递归搜索中，当搜索到p时，它的一侧（可能是左或右）将继续搜索并可能找到q，而另一侧将返回`None`。由于p节点已经找到了q，递归将会在p处停止并将p作为结果返回。同样，如果q是p的祖先，也会有类似的处理。因此在这种情况下，p或q本身会被返回作为最低公共祖先。
这种实现假定每个节点的值是唯一的，因为它依赖于节点值来判断是否找到了p或q。如果树中存在具有相同值的多个节点，这可能会导致错误地识别最低公共祖先，因为函数可能会错误地将具有相同值但不是目标p或q的节点当作p或q返回。因此，在节点值可能重复的情况下，这种实现不是有效的。需要修改实现，以便它基于节点的身份（例如内存地址或唯一标识符）而不是值来比较节点。