算法经典题目:二叉树两节点的公共祖先(LCA问题)
题目
定义二叉树的节点定义如下:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
给定二叉树中的两个节点,输出这两个节点的最低公共祖先节点。
二叉查找树
如果这棵树是二叉查找树,那么从树根开始:
- 如果当前结点t 大于结点u、v,说明u、v都在t 的左侧,所以它们的共同祖先必定在t 的左子树中,故从t 的左子树中继续查找;
- 如果当前结点t 小于结点u、v,说明u、v都在t 的右侧,所以它们的共同祖先必定在t 的右子树中,故从t 的右子树中继续查找;
- 如果当前结点t 满足 u <t < v,说明u和v分居在t 的两侧,故当前结点t 即为最近公共祖先;
- 而如果u是v的祖先,那么返回u的父结点,同理,如果v是u的祖先,那么返回v的父结点。
递归思路
如果给出根节点,最简单的想法是用递归求解,代码也较简单。如下:
TreeNode* lcaRecursion(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return NULL;
if(root == p || root == q) return root;
TreeNode* l = lcaRecursion(root->left, p, q);
TreeNode* r = lcaRecursion(root->right, p, q);
// p、q分别是root的左右子树
if(l && r) return root;
// p、q在root的左子树中
if(!r) return l;
// p、q在root的右子树中
else return r;
}
在这里,时间复杂度是O(n)。上面的方法还是有所局限的,必须保证两个要查找的节点n1和n2都出现在树中。如果n1不在树中,则会返回n2为LCA,理想答案应该为NULL。要解决这个问题,可以先查找下 n1和n2是否出现在树中,然后加几个判断即可。
找公共路径思路
找公共路径的思路也很简单
- 找从根到p的路径,并存储
- 找从根到q的路径,并存储
- 遍历这两条路径,找第一个不同的节点,则第一个不同的节点之前那个节点是最近公共祖先。代码如下:
bool findNodePathFromRoot(TreeNode* root, TreeNode* node, vector<TreeNode*> &path) {
if(!node) return false;
if(!root) return false;
path.push_back(root);
if(root == node) return true;
if(findPath(root->left, node, path) || findPath(root->right, node, path)) return true;
path.pop_back();
return false;
}
TreeNode* lcaFindPath(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> p1, p2;
bool findP = findNodePathFromRoot(root, p, p1);
bool findQ = findNodePathFromRoot(root, q, p2);
if(findP && findQ) {
TreeNode* lca = NULL;
int n = p1.size() < p2.size() ? p1.size() : p2.size();
for(int i=0; i<n; i++) {
if(p1[i] != p2[i]) break;
else lca = p1[i];
}
return lca;
}
return NULL;
}
这个思路需要遍历2次树,比一次遍历的递归稍微复杂,空间复杂度是O(n),时间复杂度仍是O(n)。
上面的两种解法有一个很大的弊端就是:如需N 次查询,则总体复杂度会扩大N 倍,故这种暴力解法仅适合一次查询,不适合多次查询。
接下来的解法,是把LCA问题看成是询问式的,即给出一系列询问,程序对每一个询问尽快做出反应。故处理这类问题一般有两种解决方法: - 一种是离线的算法,Trajan算法,相当于一次批处理,一开始就知道了全部查询结果。 - 一种是在线的算法,RMQ算法,每次读入一个查询,处理这个查询,给出答案。
Trajan算法
Tarjan算法(以发现者Robert Tarjan命名)是一个在图中寻找强连通分量的算法。算法的基本思想为:任选一结点开始进行深度优先搜索dfs(若深度优先搜索结束后仍有未访问的结点,则再从中任选一点再次进行)。搜索过程中已访问的结点不再访问。搜索树的若干子树构成了图的强连通分量。其中,强连通图的结果保存可以使用并查集。
算法用集合表示一类节点,这些节点跟集合外的点的LCA都一样,并把这个LCA设为这个集合的祖先。当搜索到节点x时,创建一个由x本身组成的集合,这个集合的祖先为x自己。然后递归搜索x的所有儿子节点。当一个子节点搜索完毕时,把子节点的集合与x节点的集合合并,并把合并后的集合的祖先设为x。因为这棵子树内的查询已经处理完,x的其他子树节点跟这棵子树节点的LCA都是一样的,都为当前根节点x。所有子树处理完毕之后,处理当前根节点x相关的查询。遍历x的所有查询,如果查询的另一个节点v已经访问过了,那么x和v的LCA即为v所在集合的祖先。
如下图的示例:
假设遍历完10的孩子,要处理关于10的请求了,取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10,集合的祖先便是关键路径上距离集合最近的点。
比如:
- 1,2,5,6为一个集合,祖先为1,集合中点和10的LCA为1
- 3,7为一个集合,祖先为3,集合中点和10的LCA为3
- 8,9,11为一个集合,祖先为8,集合中点和10的LCA为8
- 10,12为一个集合,祖先为10,集合中点和10的LCA为10
得出的结论便是:LCA(u,v)便是根至u的路径上到节点v最近的点。
LCA Tarjan基本框架:
- 先用随便一种数据结构(链表就行),把关于某个点的所有询问标在节点上,保证遍历到一个点,能得到所有有关这个节点LCA 查询
- 建立并查集。注意:这个并查集只可以把叶子节点并到根节点,即getf(x)得到的总是x的祖先
- 深度优先遍历整棵树,用一个Visited数组标记遍历过的节点,每遍历到一个节点将Visite[i]设成True 处理关于这个节点(不妨设为A)的询问,若另一节点(设为B)的Visited[B]==True,则回应这个询问,这个询问的结果就是getf(B);否则什么都不做。
- 当A所有子树都已经遍历过之后,将这个节点用并查集并到他的父节点(其实这一步应该说当叶子节点回溯回来之后将叶子节点并到自己,并DFS另一子树)
- 当一颗子树遍历完时,这棵子树的内部查询(即LCA在这棵子树内部)都已经处理了
具体的图示过程可以参考:最近公共祖先LCA问题
若二叉树有n个节点,批查询量为Q,那么算法的时间复杂度为O(n+Q)。
代码如下:
unordered_map<TreeNode*,TreeNode*> parent;
unordered_map<TreeNode*,bool> visited;
TreeNode* left;
TreeNode* right;
TreeNode* ans;
TreeNode* find(TreeNode* x) {
return parent[x] = parent[x] == x ? x : find(parent[x]);
}
void union(TreeNode* x, TreeNode* y){
TreeNode* a = parent[x];
TreeNode* b = parent[y];
parent[b] = a;
}
void lcaTrajanFind(TreeNode* u) {
if(u == NULL)
return;
parent[u] = u;
if(u->left) {
lcaTrajanFind(u->left);
union(u, u->left);
}
if(u->right){
lcaTrajanFind(u->right);
union(u,u->right);
}
visited[u] = true;
if(u==left && visited.find(right)!=visited.end()){
ans = find(right);
}
else if(u == right && visited.find(left)!=visited.end()){
ans = find(left);
}
}
TreeNode* lcaTrajan(TreeNode* root, TreeNode* p, TreeNode* q) {
left = p;
right = q;
lcaTrajanFind(root);
return ans;
}
RMQ算法
待续
线段树算法
待续