LCA离线算法Tarjan（2）案例1——求二叉树中节点的最大距离

不搞ACM，就举个笔试面试题库里的题目说一下Tarjan算法的应用吧。这是“结构之法 算法之道”上的100题里面第11题，题目如下：

 

求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，
父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。

 

不多介绍了，这个将LCA的代码该很少的部分就可以直接应用。暂时没有想出来很好的可以通用的并查集、Tarjan算法接口，所以就先重复代码解决问题吧。

这个问题只需要引申一下就很清晰了：

 

问题为：找距离最近公共祖先的距离最长的两个点

LCA问题：计算每个节点的层次，计算两个节点到最近公共节点的层次和为距离

 

代码如下，有点长，带了个简单测试用例：

 

public class Questions11 {

	public static void main(String[] args){
		/*
		 *    0
		 *  1   2
		 * 3 4
		 */
		
		List<Node<Integer>> list = new ArrayList<Node<Integer>>();
		for(int i=0; i<5; i++){
			list.add(new Node<Integer>(i));
		}
		
		list.get(0).children.add(list.get(1));
		list.get(0).children.add(list.get(2));
		
		list.get(1).children.add(list.get(3));
		list.get(1).children.add(list.get(4));
		
		solve(list.get(0), list);
	}
	
	//找距离最近公共祖先的距离最长的两个点
	//计算每个节点的层次，计算两个节点到最近公共节点的层次和为距离
	public static void solve(Node<Integer> root, List<Node<Integer>> allNodes){
		LCA_Tarjan<Integer> lca = new LCA_Tarjan<Integer>();
		assertEquals(3, lca.getMaxDistance(root,allNodes));
	}
	
	public static class LCA_Tarjan<T> {
		
		public static class Node<T>{  
		    T data;         //Node的数据
		    int level = 0;
		    Node<T> father; //父节点/祖先节点
		    List<Node<T>> children;
		    
		    public Node(){}
		    
		    public Node(T data){  
		        this.data = data;  
		        this.father = this;
		        children = new ArrayList<Node<T>>();
		    }
		}  
		
		public static class Pair<T>{
			Node<T> p, q;
			Node<T> lca;
			public Pair(Node<T> p, Node<T> q){
				this.p = p;
				this.q = q;
			}
		}

		List<Node<T>> allNodes;
		Map<Node<T>,Boolean> checked;
		int maxLen = 0;
		
		public int getMaxDistance(Node<T> root, List<Node<T>> allNodes){
			this.allNodes = allNodes;
			checked = new HashMap<Node<T>,Boolean>();
			LCA(root,0);
			return maxLen;
		}
		
		private void LCA(Node<T> u, int level){
			for(Node<T> v:u.children){
				LCA(v, level++);
				union(u, v);
			}
			checked.put(u, true);
			u.level = level;
			for(Node<T> n:allNodes){
				if(n==u)
					continue;
				Boolean b = checked.get(n);
				if(b!=null && b){
					int fatherLevel = find(n).level;
					if(maxLen<(u.level+n.level-2*fatherLevel))
						maxLen = u.level+n.level-2*fatherLevel;
				}
			}
		}
		
		//--------------------------------------------------------------------
		//并查集
		    
		/**
		 * 找到祖先节点
		 * @param x
		 * @return
		 */
		public Node<T> find(Node<T> x){  
			//当自己是祖先的时候直接返回
			if (x == x.father){
				return x;
			}
			
			//当自己的父节点不是祖先的时候，压缩树直接连接到祖先节点
			x.father = find(x.father);
			
			return x.father;
		}  
		  
		/**
		 * x和y节点之间有连接，将其所属集合连接。rank值小的树加到rank值大的树下面。相同时y加到x下。
		 * @param x
		 * @param y
		 */
		public void union(Node<T> x, Node<T> y){ 
			Node<T> xFather = find(x);
			Node<T> yFather = find(y);
			//当两个结合不联通的时候根据rank值，将rank值小的树加到rank值大的树下面
			if(xFather==yFather){
				return;
			}else{
				yFather.father = xFather;
			}
		}  
	}
}

 

做完看到编程之美上有这个题目，还没仔细看解法，这里主要是说一下LCA怎么用在这个题，这样做下来还是挺简单的，而且时间复杂度LCA只有O(n+Q)，还不错了