利用Tarjan算法解决（LCA）二叉搜索树的最近公共祖先问题——数据结构

柔光的暖阳◎ 2021-12-14 09:11 186阅读 0赞

相关知识：（来自百度百科）

** LCA**（Least Common Ancestors）

即最近公共祖先，是指在**有根树**中，找出某两个结点u和v最近的公共祖先。

![1497599-20190425105700437-436920119.jpg][]

例如：

1和7的最近公共祖先为5；

1和5的最近公共祖先为5；

7和5的最近公共祖先为7；

--------------------

题目：

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

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

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

![binarysearchtree_improved.png][]

**示例 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 为不同节点且均存在于给定的二叉搜索树中。

--------------------

常见解法：

1.暴力枚举（朴素算法）

遍历树，找到两个节点（A、B）的位置。

将深度较深的节点（A）向树的根部移动到和深度较浅的节点（B）同一深度。

然后两个点一起向上移动，直到重叠。

![1497599-20190425172438142-332892900.png][]

2.运用DFS序

3.倍增寻找（ST算法）

4.Tarjan算法（离线算法）

5.树链剖分

--------------------

分析：

这里讨论一下Tarjan算法（因为只看懂了这个）

[Tarjan算法][Tarjan]其实是一种由Robert Tarjan提出的求解**有向图强连通分量**的线性时间的算法。

如果把LCA看作一个图的话，就是**求连接图中两个元素的最短路径**。

而这个算法是基于**并查集**（两个元素是否同一上级）和**DFS**（深度优先搜索）

DFS的作用是深度遍历整个树，并查集的作用是将该点和其子节点连接成一个集合：如下图每种颜色代表一个集合

![1497599-20190425195207655-676625613.png][]

个人的理解：

① 如果在上图中找2和8的最近公共祖先，从根节点1开始深度遍历，会首先得到**蓝色这个集合**（2在集合中）。

② 但在遍历的过程中发现**蓝色集合**里面没有8，那么就说明8在其他颜色的集合里面。

③ 而**蓝色集合**与其他颜色集合连接点为1，不用考虑8在哪个集合中，就能够断定2和8的最近公共祖先是1。

--------------------

Tarjan代码实现：

/**
     * 对二叉树节点的定义
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    
    
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
            if(root == NULL)//若根节点为空，返回NULL
                return NULL;
            if(root == p || root == q)//当q为p的父节点或p为q的父节点
                return root;
            
            //这里通过递归实现LCA
            TreeNode* left = lowestCommonAncestor(root->left, p, q);
            TreeNode* right = lowestCommonAncestor(root->right, p, q);
            
            if(left != NULL && right != NULL)
                return root;
            else if(left != NULL)
                return left;//移到节点的左孩子
            else if(right != NULL)
                return right;//移到节点的右孩子
            else 
                return NULL;
            
        }
    };

转载于:https://www.cnblogs.com/yi2105/p/10769908.html

[1497599-20190425105700437-436920119.jpg]: /images/20211214/52b3322ffb234b19b1dbe240997f8d00.png
[binarysearchtree_improved.png]: /images/20211214/bf41862a0ee940ef911562975932793e.png
[1497599-20190425172438142-332892900.png]: /images/20211214/82c3520371ae4101b1db572103c18e3f.png
[Tarjan]: https://baike.baidu.com/item/tarjan%E7%AE%97%E6%B3%95/10687825?fr=aladdin
[1497599-20190425195207655-676625613.png]: /images/20211214/8654305025644d33be6247ff87eddcb7.png