博客主页：@花无缺 欢迎 点赞 收藏⭐ 留言 加关注✅! 本文由 花无缺 原创
收录于专栏 【力扣题解】
文章目录
【力扣题解】P236-二叉树的最近公共祖先-Java题解题目描述题解总结
【力扣题解】P236-二叉树的最近公共祖先-Java题解
P236-二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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, 105] 内。-109 <= Node.val <= 109所有 Node.val 互不相同 。p != qp 和 q 均存在于给定的二叉树中。
题解
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 空树, 返回 null
// 当前节点是 p 节点, 那么直接返回 p, 说明 p 就是 p, q 的祖先节点
// 当前节点是 q 节点, 那么直接返回 q, 说明 q 就是 p, q 的祖先节点
if (root == null || root == p || root == q) {
return root;
}
// 递归遍历左子树和右子树
// 搜索左子树和右子树中是否有 p 或 q
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 如果左右子树的搜索结果都不为空, 说明 p 和 q 都在左右子树中找到了
// 当前节点肯定就是 p, q 的祖先节点, 直接返回 root
if (left != null && right != null) {
return root;
}
// 如果 left 为空, right 不为空, 那么祖先节点就在右子树中
// 结果就是 right, 直接返回
if (left == null && right != null) {
return right;
// 如果 left 不为空, right 为空, 那么祖先节点就在左子树中
// 直接返回 left
} else if (left != null && right == null) {
return left;
// 否则 left 和 right 都为空
// 说明没有找到公共祖先, 返回 null
} else {
return null;
}
}
时间复杂度：O(n)，要搜索整个二叉树，遍历所有节点，节点数为 n。
总结
这个题目要求我们查找两个节点的最近公共祖先节点，那么我们肯定需要自底向上的搜索节点，因为只有自底向上的搜索才会找到两个节点最近的公共祖先节点，那么我们就想到了回溯，先遍历最底层的节点，如果不满足条件，再回溯到上层的节点查找，那么我们就可以使用后序遍历（左右中），后序遍历就是很自然的回溯过程。
此处我们使用的是递归的写法，那么递归的终止条件如何确定呢？首先假设我们从根节点开始出发，如果当前节点是空节点，说明这是一棵空树，那么递归肯定要终止，并且返回 null。另外，如果根节点就是 p 节点或者 q 节点，那么 p 和 q 的公共祖先节点就是根节点，因为如果根节点就是 p（q），那么另外一个节点 q（p）肯定就是当前节点（根节点）的子节点，所以根节点就是公共祖先节点。
所以递归的终止条件为：
// 空树, 直接返回 null
if (root == null) {
return null;
}
// 当前节点是 p 节点, 那么直接返回 p, 说明 p 就是 p, q 的祖先节点
// 当前节点是 q 节点, 那么直接返回 q, 说明 q 就是 p, q 的祖先节点
if (root == p || root == q) {
return root;
}
接下来我们就要进行后序遍历了，先遍历左子树，再遍历右子树：
而且我们要将左右子树递归的结果保存下来，因为在回溯到中间节点的时候，我们需要使用左右子树递归的结果。
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
然后遍历中间节点：
如果说左右子树返回的结果都不为空，那么说明左右子树都分别找到了 p 和 q 节点，那么说明当前节点就是他们的最近公共祖先节点。
如果有一个子树的结果为空，那么说明他们的祖先节点就在另一棵子树，那么直接返回另一棵子树的结果。
如果两棵树都为空，那么说明搜索完了整棵树都没有找到符合题意的公共祖先，直接返回 null；
// 如果 left 为空, right 不为空, 那么祖先节点就在右子树中
// 结果就是 right, 直接返回
if (left == null && right != null) {
return right;
// 如果 left 不为空, right 为空, 那么祖先节点就在左子树中
// 直接返回 left
} else if (left != null && right == null) {
return left;
// 否则 left 和 right 都为空
// 说明没有找到公共祖先, 返回 null
} else {
return null;
}
作者：花无缺(huawuque404.com)
欢迎关注我的博客：花无缺-每一个不曾起舞的日子都是对生命的辜负~ 一起进步-刷题专栏：【力扣题解】 磊往期精彩好文： 【全网最全爱心代码仓库】 【CSS选择器全解指南】 【HTML万字详解】 你们的点赞 收藏⭐ 留言 关注✅ 是我持续创作，输出优质内容的最大动力！ 谢谢！
参考阅读
您阅读本篇文章共花了：
发表评论