DeepSeek LeetCode 236. 二叉树的最近公共祖先 Java实现

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

思路：递归后序遍历

从根节点开始递归：

· 如果当前节点为空，或当前节点就是 p 或 q，直接返回当前节点。
· 分别递归左右子树，得到 left 和 right。
· 如果 left 和 right 都非空，说明 p 和 q 分别在左右两侧，当前节点就是最近公共祖先。
· 否则，返回非空的那一个（说明两个目标节点都在同一侧，或只找到了其中一个）。

Java 代码

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);

// 左右都找到了，说明 p、q 分布在两侧，当前节点就是 LCA
if (left != null && right != null) {
return root;
}

// 否则返回非空的那一侧
return left != null ? left : right;
}
}

复杂度分析

· 时间复杂度：O(n)，每个节点最多访问一次。
· 空间复杂度：O(h)，递归栈深度为树高。最坏情况下（链状树）为 O(n)。

示例

// 树结构：
// 3
// / \\
// 5 1
// / \\ / \\
// 6 2 0 8
// / \\
// 7 4

p = 5, q = 1 → 3
p = 5, q = 4 → 5
p = 6, q = 4 → 5

关键点

· 递归函数含义：在以 root 为根的子树中，寻找 p 和 q 的最近公共祖先。
· 如果当前节点就是 p 或 q，直接返回它，因为不可能再往下找到更近的祖先。
· 左右子树返回值都非空，说明两个目标节点分居两侧，当前节点即为答案。
· 只需要一次 DFS，无需额外存储路径。

附：迭代写法（父指针 + 祖先集合）

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Map<TreeNode, TreeNode> parent = new HashMap<>();
Deque<TreeNode> stack = new ArrayDeque<>();
parent.put(root, null);
stack.push(root);

// 遍历整棵树，记录每个节点的父节点
while (!parent.containsKey(p) || !parent.containsKey(q)) {
TreeNode node = stack.pop();
if (node.left != null) {
parent.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parent.put(node.right, node);
stack.push(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;
}
}

迭代写法时间复杂度 O(n)，空间复杂度 O(n)，适合不想用递归或树很深的情况。