LeetCode 236. 二叉树的最近公共祖先

Categories:

Tags:

题目描述
思路分析
1. 解法一：递归 DFS（推荐）
2. 解法二：父指针 + 哈希集合
相似题目

题目描述

✅ 236. 二叉树的最近公共祖先

题目：

给定一棵二叉树，找到两个指定节点 p 和 q 的最近公共祖先（LCA）。最近公共祖先定义为：对于树的两个节点 p、q，是它们的祖先中深度最大的节点（一个节点也可以是自身的祖先）。

示例 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 均存在于给定的树中

思路分析

解法一：递归 DFS（推荐）

核心思路：

LCA 有两种情况：①p 和 q 分别在某节点的左右子树 → 该节点就是 LCA；②p 是 q 的祖先（或反之）→ 较高的节点就是 LCA。

递归语义：root 为 nil/p/q 时直接返回 root；否则递归左右子树得 left/right：两者均非空 → 当前节点是 LCA；只有一侧非空 → 返回非空侧。

情况 ② 正确性：递归到 p 时直接返回 p，不再深入找 q，最终 left=p，right=nil，返回 p，正确。

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数，最坏情况遍历所有节点

空间复杂度：O(h)，其中 h 为树高，递归栈深度

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root; // p 和 q 分列两侧，当前节点是 LCA
        }
        return left != null ? left : right;
    }
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root
	}

	// 递归查找左右子树
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)

	// 如果左右都不为空，说明当前节点是最近公共祖先
	if left != nil && right != nil {
		return root
	}

	// 否则返回非空的那一边
	if left != nil {
		return left
	}
	return right
}

解法二：父指针 + 哈希集合

核心思路：

BFS 建立每个节点到父节点的 parent 映射；从 p 出发沿 parent 链向上收集所有祖先到集合；从 q 出发向上，第一个出现在集合中的节点即 LCA。

适合需要多次查询 LCA 的场景，可预处理 parent 映射后复用。

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数

空间复杂度：O(n)，存储父节点映射和祖先集合

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        parent.put(root, null);
        queue.offer(root);
        // BFS 建立父节点映射，直到 p 和 q 都被发现
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                parent.put(node.left, node);
                queue.offer(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                queue.offer(node.right);
            }
        }
        // 收集 p 的所有祖先
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        // q 沿父链上行，找第一个在 p 祖先集合中的节点
        while (!ancestors.contains(q)) {
            q = parent.get(q);
        }
        return q;
    }
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// 使用队列进行层序遍历，建立父节点映射
	queue := []*TreeNode{root}
	parent := make(map[*TreeNode]*TreeNode)

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node.Left != nil {
			parent[node.Left] = node
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			parent[node.Right] = node
			queue = append(queue, node.Right)
		}
	}

	// 查找 p 的所有祖先
	ancestors := map[*TreeNode]bool{}
	for p != nil {
		ancestors[p] = true
		p = parent[p]
	}

	// 查找 q 的祖先，找到第一个出现在 p 的祖先集合中的节点
	for q != nil {
		if ancestors[q] {
			return q
		}
		q = parent[q]
	}
	return nil
}

相似题目

题目	难度	考察点
235. 二叉搜索树的最近公共祖先	中等	利用 BST 有序性剪枝
2225. 找出输掉零场或一场比赛的玩家	中等	哈希表统计
1644. 二叉树的最近公共祖先 II	中等	p/q 可能不在树中
1650. 二叉树的最近公共祖先 III	中等	节点有父指针，类似链表相交
1676. 二叉树的最近公共祖先 IV	中等	多个目标节点的 LCA
2096. 从二叉树一个节点到另一个节点每一步的方向	中等	LCA 求路径
2509. 查询树中环的长度	困难	LCA、位运算
1123. 最深叶节点的最近公共祖先	中等	后序遍历求深度 + LCA

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/69502621