难度: Medium
Submission
运行时间: 33 ms
内存: 19.1 MB
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
p_parents = findParent(p)[::-1]
q_parents = findParent(q)[::-1]
i = 0
while i < min(len(p_parents), len(q_parents)) and p_parents[i].val == q_parents[i].val:
i += 1
return p_parents[i - 1]
def findParent(node):
parent = []
while node:
parent.append(node)
node = node.parent
return parent
Explain
此题解采用了父指针迭代的方法来查找二叉树的最近公共祖先。首先，定义一个辅助函数 findParent 用来收集从给定节点到根节点的路径。对于每个节点 p 和 q，使用 findParent 函数生成两个列表 p_parents 和 q_parents，分别存储从根节点到 p 和 q 的路径。然后，将两个列表逆序，从根节点开始比较，找出最后一个相同的节点，即为最近公共祖先。
时间复杂度: O(h)
空间复杂度: O(h)
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
# 找到从 p 到根节点的路径并逆序
p_parents = findParent(p)[::-1]
# 找到从 q 到根节点的路径并逆序
q_parents = findParent(q)[::-1]
i = 0
# 比较两个路径找到最后一个相同的节点
while i < min(len(p_parents), len(q_parents)) and p_parents[i].val == q_parents[i].val:
i += 1
# 返回最近公共祖先
return p_parents[i - 1]
def findParent(node):
parent = []
# 从节点向上遍历到根节点，收集所有祖先
while node:
parent.append(node)
node = node.parent
return parent
"""
Explore
是的，使用父指针迭代方法要求每个节点都必须有一个有效的父指针指向其父节点。如果节点的父指针为null，这通常意味着该节点是根节点。在实现中，当遇到父指针为null的情况时，应当停止向上追溯，因为已经到达了树的根部。
在此题解中，应该直接比较节点对象而非节点的值，以避免由于节点值重复导致错误判断的情况。比较节点对象能确保即使两个不同的节点具有相同的值，也不会被错误地认为是相同的节点。因此，应该使用 `p_parents[i] == q_parents[i]` 而非 `p_parents[i].val == q_parents[i].val` 来进行比较。
如果p和q是相同的节点，那么在比较过程中，i将增加到1（因为至少有一个相同的节点，即它们自身），所以访问p_parents[i - 1]时i - 1为0，这是有效的索引，不会导致数组越界。因此，该实现在p和q为相同节点的情况下是安全的。
是的，此算法能有效处理这种情况。因为算法是通过追踪两个节点到根节点的路径来确定最近公共祖先的。如果一个节点是另一个节点的直接祖先，那么在比较两个路径时，这个祖先节点将是两个列表中首个不同的节点之前的最后一个相同节点。因此，算法只需关注两个节点到根的路径，而不需要遍历整棵树。