二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 。
解题思路
递归的方式来实现，递归的过程中，对每个节点都进行深度优先搜索
- 1、从根节点开始递归遍历二叉树。
- 2、当遍历到节点时，分别在其左右子树中递归查找目标节点。
- 3、如果左子树和右子树中都能找到目标节点，则当前节点就是最近公共祖先。
- 4、如果只在左子树或右子树中找到目标节点，则返回找到的节点作为当前节点的祖先。
- 5、如果两个目标节点都不在当前节点的子树中，则返回null。
Java实现
public class LowestCommonAncestor {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
// 3
// / \
// 5 1
// / \ / \
// 6 2 0 8
// / \
// 7 4
// 在左子树中查找最近公共祖先
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();
// 构造二叉树
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.right.left; // 节点5
TreeNode q = root.right.right; // 节点1
TreeNode result = solution.lowestCommonAncestor(root, p, q);
System.out.println(result.val); // 输出 3
}
}
时间空间复杂度
时间复杂度：O(N)，其中N是二叉树中节点的数量，因为我们需要遍历整个二叉树来寻找最近公共祖先。
空间复杂度：O(H)，其中H是二叉树的高度，因为递归调用栈的深度取决于二叉树的高度。
