剑指Offer系列（java版，详细解析）68.树中两个节点的最低公共祖先
题目一
题目描述
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
难度简单122收藏分享切换为英文接收动态反馈
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
解题思路
明确一点即可：
二叉查找树中，两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。
自己解题
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root != null) {
if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
root = root.right; // 遍历至右子节点
else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
root = root.left; // 遍历至左子节点
else break;
}
return root;
}
}
题目二
题目描述
给定一棵普通树和两个节点，求这两个节点的最低公共祖先。在这棵树中的节点具有父节点的指针。
解题思路
这道题目就会退化为 两个链表的第一个公共节点 问题。
题目三
题目描述
给定一棵普通树和两个节点，求这两个节点的最低公共祖先。
解题思路
在左右子树中查找是否存在 p 或者 q，如果 p 和 q 分别在两个子树中，那么就说明根节点就是最低公共祖先。（但是要保证最低公共祖先）
为了避免重复查找，我们可以借助辅助空间保存从根节点到p和q的两条路径。
剩下的问题就是求这两条路径的最后一个公共节点。
参考解题
以二叉树为例：
/**
* 普通树中两个节点的最低公共祖先
*/
public class Solution1 {
/**
* 求二叉树中两个节点的最低公共祖先
*
* @param root
* @param p
* @param q
* @return
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 防止特殊输入
if (root == null || p == null || q == null) {
return null;
}
ArrayList<TreeNode> pPath = new ArrayList<TreeNode>();
ArrayList<TreeNode> qPath = new ArrayList<TreeNode>();
// 寻找p、q路径
findPath(root, p, pPath);
findPath(root, q, qPath);
// 寻找p、q路径的最后一个公共节点
int minLength = Math.min(pPath.size(), qPath.size());
int LCA = 0;
for (int i = 0; i < minLength; i++) {
if (pPath.get(i) == qPath.get(i)) {
LCA = i;
}
}
return pPath.get(LCA);
}
/**
* 查找从根节点到目标节点的路径
*
* @param root
* @param target
* @param path
* @return
*/
public boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
if (root == null) {
return false;
}
path.add(root);
if (root == target) {
return true;
}
if (findPath(root.left, target, path) || findPath(root.right, target, path)) {
return true;
}
path.remove(path.size() - 1);
return false;
}
}