22. 二叉树的最近公共祖先:找出二叉树中两个节点的最近公共祖先
大约 3 分钟
找出二叉树中两个节点的最近公共祖先(Lowest Common Ancestor, LCA)是经典的树结构问题。最近公共祖先是指在二叉树中,节点 p
和 q
的最低公共祖先节点 LCA
是一个节点,使得 LCA
是节点 p
和 q
的祖先,并且 LCA
的深度是所有公共祖先中最大的。
1. 问题描述
给定一棵二叉树和树中的两个节点 p
和 q
,找出这两个节点的最近公共祖先。
2. 算法思路
为了找到这两个节点的最近公共祖先,可以使用递归的方法。基本思路是从根节点开始递归遍历树,判断以下几种情况:
- 如果当前节点是
p
或q
,那么当前节点就是p
或q
的祖先节点。 - 在左子树中查找
p
和q
的公共祖先。 - 在右子树中查找
p
和q
的公共祖先。 - 如果
p
和q
分别在当前节点的左右子树中,那么当前节点就是p
和q
的最近公共祖先。 - 如果
p
和q
都在左子树或右子树中,那么公共祖先在左子树或右子树中,返回找到的那个子树中的结果。
3. 代码实现
下面是 Java 代码的实现:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class LowestCommonAncestor {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 如果当前节点为空,或者当前节点就是 p 或 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 分别在当前节点的左右子树中,那么当前节点就是最近公共祖先
if (left != null && right != null) {
return root;
}
// 如果 p 和 q 都在左子树中,返回左子树中的最近公共祖先
return left != null ? left : right;
}
public static void main(String[] args) {
LowestCommonAncestor solution = new LowestCommonAncestor();
// 构造一个二叉树:
// 3
// / \
// 5 1
// / \ / \
// 6 2 0 8
// / \
// 7 4
TreeNode root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);
TreeNode p = root.left; // 节点 5
TreeNode q = root.left.right.right; // 节点 4
TreeNode ancestor = solution.lowestCommonAncestor(root, p, q);
System.out.println("Lowest Common Ancestor of nodes " + p.val + " and " + q.val + " is: " + ancestor.val);
}
}
4. 示例解释
假设我们有如下二叉树:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
- 设
p
是节点5
,q
是节点4
。 - 遍历树时:
- 在根节点
3
中,递归检查左子树和右子树。 - 在左子树
5
中,找到了p
节点,并递归检查5
的子树,在5
的右子树中找到了q
节点。 - 因为
p
和q
都位于5
的子树中,且5
节点是p
节点,因此5
就是p
和q
的最近公共祖先。
- 在根节点
5. 复杂度分析
- 时间复杂度:O(n),其中 n 是二叉树中的节点数。最坏情况下,需要遍历树的所有节点。
- 空间复杂度:O(h),其中 h 是二叉树的高度。由于递归调用栈的空间占用为 O(h)。
6. 总结
通过递归遍历二叉树,可以高效地找到两个节点的最近公共祖先。这个方法直观易懂,适用于普通二叉树和二叉搜索树。在处理二叉树问题时,使用递归往往能以简洁的方式解决复杂问题。