难度: Medium
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 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 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
提示：
[2, 105] 内。-109 <= Node.val <= 109Node.val 互不相同 。p != qp 和 q 均存在于给定的二叉树中。运行时间: 68 ms
内存: 25.5 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':
if root is None or p == root or q == root:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left is None and right is None:
return
if left is None:
return right
if right is None:
return left
return root
该题解采用递归的方式来查找两个节点 p 和 q 的最近公共祖先。递归函数对当前节点 root 进行如下处理： 1. 如果 root 为空，或者 root 等于 p 或 q，则直接返回 root。 2. 递归查找 root 的左子树和右子树，分别得到左子树和右子树中 p 和 q 的最近公共祖先 left 和 right。 3. 如果 left 和 right 都为空，说明在当前子树中没有找到 p 和 q，返回 None。 4. 如果 left 为空，right 不为空，则说明 p 和 q 都在右子树中，返回 right。 5. 如果 right 为空，left 不为空，则说明 p 和 q 都在左子树中，返回 left。 6. 如果 left 和 right 都不为空，说明 p 和 q 分别在左右子树中，则当前节点 root 就是最近公共祖先，返回 root。
时间复杂度: 平均 O(logn)，最坏 O(n)
空间复杂度: 平均 O(logn)，最坏 O(n)
# 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':
# 如果当前节点为空或等于 p 或 q，直接返回当前节点
if root is None or p == root or q == root:
return root
# 递归查找左子树
left = self.lowestCommonAncestor(root.left, p, q)
# 递归查找右子树
right = self.lowestCommonAncestor(root.right, p, q)
# 如果左右子树都没找到，返回 None
if left is None and right is None:
return
# 如果右子树没找到，返回左子树的结果
if left is None:
return right
# 如果左子树没找到，返回右子树的结果
if right is None:
return left
# 如果左右子树都找到了，说明当前节点就是最近公共祖先，返回当前节点
return root
在递归查找过程中，如果当前节点的左子树返回了一个非空节点（left），这意味着左子树中至少包含 p 或 q 中的一个；同样，右子树返回了一个非空节点（right），这意味着右子树中至少包含另一个。因此，如果 left 和 right 都不为空，这表明 p 和 q 分别位于当前节点的两侧，即一个在左子树，另一个在右子树。由于最近公共祖先定义为“对于任意两个节点，以最低节点作为其共同的祖先”，因此当前节点 root 必然是 p 和 q 的最近公共祖先。
返回 None 的条件是基于当前子树中不存在 p 和 q 的情况。当递归到某个节点时，如果左右子树的递归返回都是 None，这说明在该节点的左右子树中都没有找到 p 或 q。这种设计有效地涵盖了所有必要的情形，即如果 p 和 q 本身就不存在于树中，或者当前递归分支不包含这两个节点。因此，当前设计的返回 None 的逻辑是完备的，没有未涵盖的情况。
在非完全二叉树中，p 和 q 的位置确实可以影响算法的效率。如果 p 和 q 靠近树的根部，算法可能会更快找到最近公共祖先，因为递归深度较浅；相反，如果 p 和 q 位于树的较深层次，尤其是如果它们位于树的不同侧且位置偏低，那么算法需要更深层次的递归调用才能确认它们的位置并最终确定公共祖先。因此，p 和 q 的深度和它们相对于树根的位置直接影响递归调用的次数和算法的运行时间。