难度: Medium
Submission
运行时间: 124 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', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
res = None
def helper(node):
nonlocal res
if not node or res:
return
lfound = helper(node.left)
rfound = helper(node.right)
if lfound and rfound or ((lfound or rfound) and node in (p, q)):
res = node
return node
if node is p or node is q:
return node
return lfound or rfound
helper(root)
return res
Explain
这个解法使用了递归的方式来查找二叉树的最近公共祖先。递归函数 `helper` 从根节点开始，对二叉树进行后序遍历（即先探索子节点，再处理当前节点）。在探索过程中，当到达叶节点或已找到最近公共祖先时，递归会回溯。在每个节点，函数检查其左右子节点是否包含节点 p 或 q。如果当前节点自身是 p 或 q，或其任一子树包含 p 或 q，该节点会向其父节点报告这一发现。如果一个节点的两个子树各包含一个目标节点（p 或 q），那么该节点就是最近的公共祖先。为保存这个结果，使用了一个非局部变量 `res`。当找到最近公共祖先后，无需进一步递归，因此可以提前结束递归过程。
时间复杂度: 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':
res = None # 用于存储最近公共祖先的节点
def helper(node):
nonlocal res # 允许访问函数外的 `res` 变量
if not node or res: # 如果节点为空或已找到结果，则停止递归
return
lfound = helper(node.left) # 检查左子树中是否有 p 或 q
rfound = helper(node.right) # 检查右子树中是否有 p 或 q
# 如果左右子树各找到一个目标节点或当前节点是目标节点之一，设置当前节点为结果
if lfound and rfound or ((lfound or rfound) and node in (p, q)):
res = node
return node
if node is p or node is q: # 如果当前节点是 p 或 q，返回当前节点
return node
return lfound or rfound # 返回找到的目标节点
helper(root)
return res
Explore
在`helper`函数中，返回值用于表示当前节点或其子树是否包含目标节点p或q。如果当前节点是p或q，或者其左右子树中至少有一边含有p或q，则返回当前节点。这样，如果一个节点的左右子树分别返回p和q（表示两边各含有一个目标节点），那么当前节点即为p和q的最近公共祖先。返回逻辑具体为：1. 如果当前节点为空或已找到最近公共祖先，返回null；2. 递归检查左右子树；3. 如果左右子树各返回一个目标节点，或者当前节点是p或q且其一边子树包含另一个目标节点，则当前节点为公共祖先；4. 否则，返回包含p或q的子树。
`nonlocal res`关键字用于在`helper`内部函数中访问并修改外部函数`lowestCommonAncestor`中定义的变量`res`。在Python中，内部函数默认不能修改外部函数的局部变量，除非声明为`nonlocal`。这允许`helper`函数在发现最近公共祖先时直接修改`res`的值，保持最近公共祖先的状态跨多次递归调用一致。
这一逻辑通过递归函数`helper`返回值实现。当递归到一个节点，首先检查其左右子树是否包含p或q（通过调用`helper(node.left)`和`helper(node.right)`）。如果任一子树返回非null（即找到p或q），或者当前节点自身是p或q，则通过`return node`将这个节点返回给调用它的父节点。这样，每个父节点都能知道其子节点是否包含p或q。具体反映在代码中的`if node is p or node is q`和`return lfound or rfound`部分。
当发现左右子树各找到一个目标节点时，`res`被设置为当前节点。然而，递归调用并不会立即全局停止，因为当前递归路径的返回并不会停止其他正在执行的递归调用。虽然`res`已经设置，但其他分支的递归调用仍会继续执行至它们自然结束或检测到`res`非空而提前返回。这意味着虽然最近公共祖先已经找到，但程序可能仍在执行其他不必要的递归调用。