聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

程序员编程艺术第三十九~四十章:最近公共祖先LCA问题、打印螺旋矩阵

2014-01-16 06:20 浏览: 918693 次 我要评论(0 条) 字号:

    第三十九~第四十章:最近公共祖先LCA问题、打印螺旋矩阵



前言

    整个编程艺术系列写到了本第三十九和第四十章,系列越写到后,对题材的选取越严格,写作过程也更困难,毕竟不是任何一个编程问题都可以收录到本系列中。

    再者,之前已写的38章尚存在诸多问题,为了和大家一起更好的改进整个系列,特把它同步到了github上,见:https://github.com/julycoding/The-Art-Of-Programming-by-July。如此,任何人都可以在github上改进本系列,包括指正bug、优化代码、重绘图片、英文翻译等等工作。

    当然,除了review已写的38章,亦会尽快加速完成后续的十二个章节。本文主要写两个问题:

  • 第三十九章、求二叉树的任意两个节点的最近公共祖先;
  • 第四十章、打印螺旋矩阵
    最后,还是这句百说不厌的老话:有何问题,欢迎随时指正,thanks。


第三十九章、最近公共祖先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;    
	}    
};    


参考文献

  1. 九月十月百度,迅雷,华为,阿里巴巴,最新校招笔试面试六十题:http://blog.csdn.net/v_july_v/article/details/11921021
  2. http://eriol.iteye.com/blog/1170465


后记

    感谢大家一直以来的关注和支持,thanks。July、二零一四年一月十五日。

作者:v_JULY_v 发表于2014-1-15 15:39:56 原文链接
阅读:569 评论:0 查看评论


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复