剑指Offer系列（java版，详细解析）68.树中两个节点的最低公共祖先

秒速五厘米 2023-01-16 05:00 103阅读 0赞

# 题目一 #

## 题目描述 ##

#### [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先][Offer 68 - I.] ####

难度简单122收藏分享切换为英文接收动态反馈

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

[百度百科][Link 1]中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。”

例如，给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\]

![img][]

**示例 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;
        }
    }

[Offer 68 - I.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Link 1]: https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin
[img]: /images/20221022/c4cd035db35841dbb803b9c75c20822e.png