难度: Medium
Submission
运行时间: 71 ms
内存: 20.3 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', nodes: 'List[TreeNode]') -> 'TreeNode':
def dfs(root):
if not root:
return None
if root in nodes:
return root
l = dfs(root.left)
r = dfs(root.right)
if not l:
return r
if not r:
return l
return root
return dfs(root)
Explain
这个题解使用了递归的深度优先搜索（DFS）来寻找最近公共祖先。函数`dfs`从二叉树的根节点开始，向下遍历每一个节点。如果当前节点为空，返回`None`。如果当前节点是待查询的节点列表`nodes`中的一个，直接返回该节点。然后递归地在左右子树上调用`dfs`函数，得到左子树和右子树的返回结果`l`和`r`。如果某一侧返回了`None`，说明这一侧没有找到任何`nodes`中的节点，因此返回另一侧的结果。如果两侧都返回了非`None`的结果，说明当前节点是两个子树返回的节点的公共祖先，因此返回当前节点。这个递归过程持续进行，直到遍历完所有节点，或找到最近的公共祖先。
时间复杂度: O(n)
空间复杂度: O(h + k)
# 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', nodes: 'List[TreeNode]') -> 'TreeNode':
def dfs(root):
# 如果当前节点为空，返回None
if not root:
return None
# 如果当前节点是目标节点之一，返回当前节点
if root in nodes:
return root
# 在左子树中搜索
l = dfs(root.left)
# 在右子树中搜索
r = dfs(root.right)
# 如果左子树返回None，返回右子树的搜索结果
if not l:
return r
# 如果右子树返回None，返回左子树的搜索结果
if not r:
return l
# 如果两子树都找到目标节点，返回当前节点作为公共祖先
return root
# 从根节点开始DFS搜索
return dfs(root)
Explore
在当前算法中，如果`nodes`列表中包含重复的节点，算法仍然可以正确地返回最近公共祖先，但这会导致性能上的一些不必要消耗，因为重复的节点每次被遇到时都会进行处理。为了提高效率，可以在算法开始之前将`nodes`列表转换成一个集合，这样可以快速检查一个节点是否在目标节点集中，并且自动去除重复项。
在题解中，判断一个节点是否属于`nodes`列表是通过简单的`in`操作实现的。这种方法在`nodes`为列表时的时间复杂度为O(n)，其中n是列表的长度。为了优化这个查找过程，可以使用集合（`set`）数据结构，因为集合的查找时间复杂度平均为O(1)。在算法开始前，将`nodes`列表转换为一个集合可以显著提高效率。
在极端倾斜的二叉树中，递归深度可能会非常高，从而导致栈溢出。为了解决这个问题，可以考虑使用迭代而非递归来实现深度优先搜索（DFS）。具体方法包括使用显式栈来模拟递归过程，或者改用广度优先搜索（BFS），使用队列来实现。这样可以避免深层递归造成的栈溢出问题。
题解中的算法确保总是返回最近的公共祖先。这是因为只有在两个不同子树中各自找到了至少一个目标节点时，当前节点才会被确定为公共祖先并返回。此时，返回的是最低的（即最近的）公共祖先，因为一旦一个节点被确定为公共祖先，递归将停止在更高的祖先节点上进行检查。