第三十九~第四十章:最近公共祖先LCA问题、打印螺旋矩阵
前言
整个编程艺术系列写到了本第三十九和第四十章,系列越写到后,对题材的选取越严格,写作过程也更困难,毕竟不是任何一个编程问题都可以收录到本系列中。
再者,之前已写的38章尚存在诸多问题,为了和大家一起更好的改进整个系列,特把它同步到了github上,见:https://github.com/julycoding/The-Art-Of-Programming-by-July。如此,任何人都可以在github上改进本系列,包括指正bug、优化代码、重绘图片、英文翻译等等工作。
当然,除了review已写的38章,亦会尽快加速完成后续的十二个章节。本文主要写两个问题:
- 第三十九章、求二叉树的任意两个节点的最近公共祖先;
- 第四十章、打印螺旋矩阵
第三十九章、最近公共祖先LCA问题
问题描述:求二叉树的任意两个节点的最近公共祖先。
题意分析
这个问题来自去年10月整理的腾讯笔试题,即此文第31题:http://blog.csdn.net/v_july_v/article/details/11921021,网上也有很多文章阐述了这个问题,然要么是阐述不够细致规范,要么千篇一律的晦涩难懂,希望本文能把这个问题阐述的明明白白。
解答这个问题之前,咱们得先搞清楚到底什么是最先公共祖先。最近公共祖先简称LCA,所谓LCA问题,是当给定一个有根树T时,对于任意两个结点u、v,要求找到一个离根最远的结点x,使得x同时是u和v的祖先,表示为LCA(T,u,v)。
那么,到底什么是最近公共祖先呢?针对一棵普通的二叉树来讲,如下图:
结点3和结点4的最近公共祖先是结点2,即LCA(3 4)=2 。在此,需要注意到当两个结点在同一棵子树上的情况,如结点3和结点2的最低公共祖先为2,即 LCA(3 2)=2。同理:LCA(5 6)=4,LCA(6 10)=1。
明确了题意,咱们便来试着解决这个问题。一般文章的做法,可能是针对是否为二叉查找树分情况讨论,想必这也是一般人最先想到的思路。除此之外,还有所谓的Tarjan算法、倍增算法、以及转换为RMQ问题(求某段区间的极值)。
下面,便来一一具体阐述这几种方法。
解法一、暴力对待
1.1、是二叉查找树
在当这棵树是二叉查找树的情况下,如下图:
那么从树根开始:
- 如果当前结点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的父结点。
代码如下所示:
//copyright@eriol 2011 //modified by July 2014 public int query(Node t, Node u, Node v) { int left = u.value; int right = v.value; Node parent = null; //二叉查找树内,如果左结点大于右结点,不对,交换 if (left > right) { int temp = left; left = right; right = temp; } while (true) { //如果t小于u、v,往t的右子树中查找 if (t.value < left) { parent = t; t = t.right; //如果t大于u、v,往t的左子树中查找 } else if (t.value > right) { parent = t; t = t.left; } else if (t.value == left || t.value == right) { return parent.value; } else { return t.value; } } }
1.2、不是二叉查找树
但如果这棵树不是二叉查找树呢?一网友何海涛在他博客中用了一种蛮力方法。由于每个结点都有一个指针指向它的父结点,于是我们可以从任何一个结点出发,得到一个到达树根结点的单向链表。因此这个问题转换为两个单向链表的第一个公共结点。
我不想再在这里重复赘述,有兴趣的可以看原文。
接下来的解法,将不再区别对待是否为二叉查找树,而是一致当做是一棵普通的二叉树。
解法二、Tarjan算法
不论咱们所面对的二叉树是二叉查找树,还是不是二叉查找树,都可以把求任意两个结点的最近公共祖先,当做是查询的问题,如果是只求一次,则是单次查询,如果要求多个任意两个结点的最近公共祖先,则相当于是批量查询。
涉及到批量查询的时候,咱们可以借鉴离线处理的方式,这就引出了解决此LCA问题的Tarjan离线算法。
Tarjan算法基于深度优先搜索。对于新搜索到的一个结点u,先创建由u构成的集合,再对u的每颗子树进行搜索,每搜索完一棵子树,这时候子树中所有的结点的最近公共祖先就是u了。它的原理是利用并查集优越的时空复杂度,可以实现O(n+q)的算法,q是查询次数。
2.1、什么是Tarjan算法
但关键是 Tarjan算法是怎么想出来的呢?给定下图,你是否能看出来:分别从结点1的左右子树当中,任取一个结点,设为u、v,这两个任意结点u、v的最近公共祖先都为1。
于此,我们可以得知:若两个结点u、v分别分布于某节点t 的左右子树,那么此节点 t即为u和v的最近公共祖先LCA。更进一步,再考虑到一个节点自己就是LCA的情况,得知:
- 若某结点t 是两结点u、v的祖先之一,且这两结点并不分布于该结点t 的一棵子树中,而是分别在结点t 的左子树、右子树中,那么该结点t 即为两结点u、v的最低公告祖先LCA。
这个定理就是Tarjan算法的基础。
一如之前我们得到的结论:“如果当前结点t 满足 u <t < v,说明u和v分居在t 的两侧,故当前结点t 即为最近公共祖先”。
对于之前我们说到的“如果要求多个任意两个结点的最近公共祖先,则相当于是批量查询”,即很多组的询问的情况下,或许可以先确定一个LCA,例如是根节点1,然后再去检查所有询问,看是否满足刚才的定理,不满足就忽视,满足就赋值,全部弄完,再去假设2号节点是LCA,再去访问一遍。
可此方法需要判断一个节点是在左子树、还是右子树,或是都不在,都只能遍历一棵树,而多次遍历的代价实在是太大了,所以我们需要找到更好的方法。
但是细心一点,我们便可以发现,若一个点的父亲会被某个点遍历到,那么该点也会被那个点遍历到,也就是说一个点只需要被遍历一遍即可,因为遍历信息是可以传递。
2.2、Tarjan算法流程
Tarjan算法流程为:
procedure dfs(i);
begin
设置i号节点的祖先为i
若i的左子树不为空,dfs(i-左子树);
若i的右子树不为空,dfs(i-右子树);
访问每一条与i相关的询问
若另一个节点已经被访问过,则输出另一个节点当前的祖先
标记i为已经访问,将所有i的孩子包括i本身的祖先改为i的父亲
end;
2.3、Tarjan算法的一个例子
引用此文中的一个例子,如下:
STEP 1 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 2 | 3 |
STEP 2 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 2 | 2 |
STEP 3 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 2 | 2 | 4 | 5 |
STEP 4 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 2 | 2 | 4 | 4 |
STEP 5 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 2 | 2 | 4 | 4 | 6 |
STEP 6 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 2 | 2 | 4 | 4 | 4 |
STEP 7 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 2 | 2 | 2 | 2 | 2 |
进行到此step7,当访问完结点2的左子树(3),和右子树(4、5、6)后,结点3、结点4、结点5、结点6这4个结点中,任意两个结点的最近公共祖先均为2。
STEP 8 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 1 | 1 | 1 | 1 | 1 |
STEP 9 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 1 | 1 | 1 | 1 | 1 | 7 |
STEP 10 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 1 | 1 | 1 | 1 | 1 | 7 | 8 |
STEP 11 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 1 | 1 | 1 | 1 | 1 | 7 | 7 |
STEP 12 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
当进行到此step12,访问完1的左子树(2、3、4、5、6),和右子树(7、8)后,结点2、3、4、5、6、7、8这7个结点中任意两个结点的最近公共祖先均为1;
STEP 13 | ||||||||
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
祖先 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
解法三、转换为RMQ问题
解决此最近公共祖先问题的还有一个算法,即为RMQ算法,未完待续..
第四十章、螺旋矩阵
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order。一句话,即为螺旋矩阵问题。
举个例子,给定如下的一个矩阵:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
你应该返回:[1,2,3,6,9,8,7,4,5]。如下图所示,遍历顺序为螺旋状:
以下是一份参考代码:
//代码来源:http://discuss.leetcode.com/questions/29/spiral-matrix。 class Solution { public: vector<int> spiralOrder(vector<vector<int> >& matrix) { vector<int> result; if (matrix.empty()) return result; ssize_t beginX = 0, endX = matrix[0].size() - 1; ssize_t beginY = 0, endY = matrix.size() - 1; while (true) { // From left to right for (ssize_t i = beginX; i <= endX; ++i) result.push_back(matrix[beginY][i]); if (++beginY > endY) break; // From top down for (ssize_t i = beginY; i <= endY; ++i) result.push_back(matrix[i][endX]); if (beginX > --endX) break; // From right to left for (ssize_t i = endX; i >= beginX; --i) result.push_back(matrix[endY][i]); if (beginY > --endY) break; // From bottom up for (ssize_t i = endY; i >= beginY; --i) result.push_back(matrix[i][beginX]); if (++beginX > endX) break; } return result; } };
参考文献
- 九月十月百度,迅雷,华为,阿里巴巴,最新校招笔试面试六十题:http://blog.csdn.net/v_july_v/article/details/11921021;
- http://eriol.iteye.com/blog/1170465;
后记
感谢大家一直以来的关注和支持,thanks。July、二零一四年一月十五日。
网友评论已有0条评论, 我也要评论