力扣百题通

236. 二叉树的最近公共祖先 (Medium)

Properties2
description给定一个二叉树，找到该树中两个指定节点的最近公共祖先（LCA）。
tags05-二叉树

10分钟阅读

236. 二叉树的最近公共祖先 (Medium)

专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

给定一个二叉树，找到该树中两个指定节点的最近公共祖先（LCA）。

最近公共祖先 的定义为： 对于有根树 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, 10^5] 内
  • -10^9 <= Node.val <= 10^9
  • 所有 Node.val 互不相同
  • p != q
  • p 和 q 均存在于给定的二叉树中

题目详细分析

  • 数据范围含义： 最多 10^5 个节点，非常大的数据量，要求 O(n) 时间、O(h) 空间的算法。递归深度可能达到 10^5（链状树），Python 默认递归深度可能不够，但面试中一般不会拿链状树来卡递归解法。迭代法更安全。
  • 输入输出特征： 输入根节点、p 节点、q 节点（都是 TreeNode 对象），输出 LCA 节点（也是 TreeNode 对象）。注意：输入的是节点引用，不是值。
  • 边界条件： p 或 q 本身就是 LCA（如示例 2）；根节点是 LCA（如示例 1）；p 和 q 在同一个子树中。
  • 核心约束： p 和 q 一定在树中，且不相等、值互不相同。这简化了问题——不需要处理找不到的情况。一个节点可以是它自己的祖先。
  • 隐藏条件： 这是二叉树（不是 BST），不能利用 BST 的大小性质来剪枝，必须遍历整棵树（或在找到 p 和 q 后提前返回）。

小白版直白理解

就像在家族族谱里找两个人的最近共同长辈——从两个人出发，分别往上找各自的祖先（父亲、爷爷、曾祖父……），第一个交汇的祖先就是最近公共祖先。实现上，我们从树根往下走：如果 p 和 q 分别在某人的左右两支上，那这个人就是最近公共祖先。如果两个人在同一个分支，就往那个分支继续找。

解题思路

思路一：后序递归（推荐）

核心思想： 用后序遍历从底向上搜索。对每个节点，递归地在左右子树中查找 p 和 q：

  • 如果左右子树都找到了（p 和 q 分布在左右两侧），当前节点就是 LCA。
  • 如果只在一边找到了，返回找到的那一边的结果。
  • 如果都没找到，返回 None。

为什么用后序？ 后序位置的特点是：在决定当前节点是不是 LCA 之前，已经知道了左右子树中是否包含了 p 和 q。这正是判断 LCA 所需要的——只有知道了左右子树的信息，才能判断当前节点是否是 p 和 q 的汇合点。

def lowestCommonAncestor(root, p, q):
    # 如果当前节点为空，或当前节点就是 p 或 q，直接返回
    if not root or root == p or root == q:
        return root
 
    # 后序：先在左右子树中查找
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
 
    # 后序位置：判断当前节点是不是 LCA
    if left and right:
        # p 和 q 分别在左右子树中 → 当前节点就是 LCA
        return root
    # 只在一边找到 → 返回找到的那边
    return left or right

代码理解： 这段代码虽然只有几行，但非常精妙。它的核心逻辑是：

  1. 如果 root 是 p 或 q，那 root 本身就可能是 LCA（如果另一个节点在 root 的子树中）。
  2. 递归左右子树，看能找到什么。
  3. 如果左右都返回非空，说明 p 和 q 分布两边，root 就是 LCA。
  4. 如果只有一边非空，说明 p 和 q 都在那一边，返回那一侧找到的结果。

思路二：记录父节点（哈希表法）

用 BFS/DFS 遍历整棵树，用哈希表记录每个节点的父节点。然后从 p 出发向上走，标记所有祖先；再从 q 出发向上走，第一个被标记过的祖先就是 LCA。

适用场景： 当需要多次查询不同的 p、q 对时，可以复用父节点信息。

from collections import deque
 
def lowestCommonAncestor(root, p, q):
    # 用 BFS 记录每个节点的父节点
    parent = {root: None}
    q_queue = deque([root])
 
    while q_queue:
        node = q_queue.popleft()
        if node.left:
            parent[node.left] = node
            q_queue.append(node.left)
        if node.right:
            parent[node.right] = node
            q_queue.append(node.right)
 
    # 从 p 向上标记所有祖先
    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
 
    # 从 q 向上找第一个共同祖先
    while q not in ancestors:
        q = parent[q]
 
    return q

易错点

  • p 或 q 本身就是 LCA 的情况： 递归法中，如果 root 是 p，直接返回 p。此时如果 q 在左子树或右子树中，返回的 p 就是正确的 LCA。不需要继续递归。
  • 后序位置的判断逻辑： left and right 的意思是左右子树 都找到了非空结果。注意：这里的非空结果不一定是 p 或 q 本身，也可能是更低层找到的 LCA。
  • return left or right 的妙用： Python 中，如果 left 非空就返回 left，否则返回 right。用一行代码代替了 if-else 判断。
  • 题目保证 p 和 q 存在： 如果题目不保证 p 和 q 存在（实测中较少见），递归法需要额外处理。
  • 节点值互不相同： 题目保证值唯一，所以可以用值作为哈希表的键（但需要注意输入是节点引用）。

框架提炼

后序 LCA 模板： 查找两个节点在二叉树中的公共祖先的标准做法。

def findLCA(root, p, q):
    if not root or root == p or root == q:
        return root
    left = findLCA(root.left, p, q)
    right = findLCA(root.right, p, q)
    if left and right:
        return root
    return left or right

推广： 这个模板可以扩展到：

  • 三叉树的多节点 LCA： 递归搜索每个子树，如果有两个及以上子树返回非空，当前节点就是 LCA。
  • BST 版本的 LCA（235-二叉搜索树的最近公共祖先）： 利用 BST 大小关系剪枝，不需要遍历整棵树。

核心思维： 后序位置是获取「左右子树信息」后做决策的位置。很多「需要知道子树状态才能决策」的问题都用后序。

关联题目

关系图谱

反向链接