最深叶节点的最近公共祖先

难度: Medium

给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。

回想一下：

叶节点 是二叉树中没有子节点的节点
树的根节点的深度为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点，它是它本身的最近公共祖先。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。

提示：

树中的节点数将在 [1, 1000] 的范围内。
0 <= Node.val <= 1000
每个节点的值都是 独一无二 的。

注意：本题与力扣 865 重复：https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/

Submission

运行时间: 29 ms

内存: 16.4 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        ans=None
        max_depth=-1
        def dfs(node,depth):
            nonlocal max_depth,ans

            if node is None:
                max_depth=max(depth,max_depth)
                return depth

            left_max_depth=dfs(node.left,depth+1)
            right_max_depth=dfs(node.right,depth+1)

            if left_max_depth==right_max_depth==max_depth:
                ans=node
            return max(left_max_depth,right_max_depth)
        dfs(root,0)
        return ans

Explain

该题目的解决方案使用了深度优先搜索（DFS）来确定所有最深叶子节点的最近公共祖先。首先，使用一个递归函数 dfs，该函数对二叉树进行遍历，并返回每个节点的最大深度。在执行过程中，它同时更新全局变量 max_depth，用于记录树中叶子节点的最大深度。对于每个节点，如果左右子树返回的深度相等并且等于 max_depth，说明该节点是最深叶子节点的公共祖先。这种方式确保了只有当节点的所有子树深度都达到最大深度时，它才会被认为是公共祖先。

时间复杂度: O(n)

空间复杂度: O(h)，其中 h 是树的高度

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        ans=None  # 用于存储最深叶节点的最近公共祖先
        max_depth=-1  # 记录最大深度
        def dfs(node, depth):
            nonlocal max_depth, ans  # 引用外部变量
            if node is None:  # 如果节点为空，则返回当前深度
                return depth
            left_max_depth = dfs(node.left, depth + 1)  # 递归获取左子树的最大深度
            right_max_depth = dfs(node.right, depth + 1)  # 递归获取右子树的最大深度
            if left_max_depth == right_max_depth == max_depth:  # 如果左右子树深度相等且等于最大深度，更新答案
                ans = node
            return max(left_max_depth, right_max_depth)  # 返回当前节点的最大深度
        dfs(root, 0)  # 从根节点开始深度为0进行DFS
        return ans  # 返回最终答案

Explore

在DFS中，当递归到空节点时，返回当前深度而不是-1是为了正确计算其父节点的深度。空节点本身代表了超出叶子节点的边界，因此返回其高度（即父节点的高度加一）能够让父节点正确判断其子树的最大深度。如果返回-1，会导致计算深度时出现错误，因为父节点的深度将会被错误地降低。

在这个DFS实现中，max_depth变量实际上并没有在dfs函数内直接更新，而是通过比较和确定是否更新ans节点来隐式处理。max_depth在逻辑上应当在遍历过程中更新为遇到的最深的叶节点深度，但具体实现依赖于外部正确设置这一值或在dfs函数外部调整。在题解中，max_depth需要事先设定为正确的最深叶节点深度，或者需要另一个遍历来确定这个值。

如果一个节点的左右子树的最大深度都等于max_depth，这意味着该节点的左右子树都至少包含一个最深的叶节点，并且这些叶节点的深度是相同的。只有在这种情况下，该节点才能被视为这些最深叶节点的最近公共祖先。如果左右子树深度不同，则表示叶节点的深度不均，不能确认该节点是所有最深叶节点的公共祖先。

如果左右子树的最大深度不相等，则当前节点的返回值应该是两者中的较大值。这是因为更深的子树代表了该子树方向上存在更深的叶节点，而当前节点的最大深度应该反映从当前节点到其所有子树中最深叶节点的最大距离。因此，返回左右子树深度的最大值确保了能够正确表示从当前节点到最深叶节点的距离。