九度Online Judge | 劍指Offer | 樹中兩個結點的最低公共祖先

題目描述：

給定一棵樹，同時給出樹中的兩個結點，求它們的最低公共祖先。

輸入：

輸入可能包含多個測試樣例。

對于每個測試案例，輸入的第一行為一個數n(0<n<1000)，代表測試樣例的個數。

其中每個測試樣例包括兩行，第一行為一個二叉樹的先序周遊序列，其中左右子樹若為空則用0代替，其中二叉樹的結點個數node_num<10000。

第二行為樹中的兩個結點的值m1與m2(0<m1,m2<10000)。

輸出：

對應每個測試案例，

輸出給定的樹中兩個結點的最低公共祖先結點的值，若兩個給定結點無最低公共祖先，則輸出“My God”。

樣例輸入：

2
1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0
6 8
1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0
6 12      

樣例輸出：

2
My God      

分析：

如果是二叉查找樹，可以利用查找樹的性質，有O(lgn)的方法。      

這裡是一棵普通的二叉樹。分為兩種情況：(1)已知每個節點的父節點;(2)不知道每個節點的父節點。      

如果不知道父節點，采用遞歸的方法，從上到下（最壞O(n^2)），或從下到上（最壞O(n)）均可，參見http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html      

如果知道父節點，可采用非遞歸的方法，也有兩種方法，利用哈希表，或利用節點的高度差（不需要額外空間），複雜度為O(h)，h為樹的高度，參見http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html      

此外，第一篇文章裡還給出了一個查找複雜度為O(sqt(n))，初始化複雜度為O(n)的方法：http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor，這個方法很像“1到100層樓，有兩個雞蛋，如何在最少次數内找到雞蛋臨界摔碎的點”的感覺，先分層，再在層裡找，不過這裡分層是均勻分的。      

下面展示的是複雜度為O(h)的非遞歸、利用節點高度差的方法，已經AC。針對這道題，建立樹的過程隻需要記錄每個節點的父節點即可，左右子節點可以無視，但建立過程複雜度已經O(n)了，還遞歸了，喧賓奪主了。- -!      

解答：

import java.util.HashMap;
import java.util.Scanner;

public class LowestCommonAncestor {
	private class TreeNode {
		int val;
		TreeNode parent;

		TreeNode(int x) {
			val = x;
		}
	}

	private HashMap<Integer, TreeNode> records = new HashMap<Integer, TreeNode>();
	private int[] preOrder;
	private int index;

	public int lowestCommonAncestor(int[] preOrder, int p, int q) {
		if (preOrder.length <= 1) {
			return 0;
		}

		this.preOrder = preOrder;
		records.clear();
		index = 0;
		buildTree(null);

		TreeNode p1 = records.get(p);
		TreeNode p2 = records.get(q);
		if (p1 == null || p2 == null) {
			return 0;
		}
		int h1 = getHeight(p1);
		int h2 = getHeight(p2);

		if (h1 > h2) {
			int tmp = h1;
			h1 = h2;
			h2 = tmp;

			TreeNode tmpNode = p1;
			p1 = p2;
			p2 = tmpNode;
		}

		int dh = h2 - h1;
		for (int h = 0; h < dh; ++h) {
			p2 = p2.parent;
		}

		while (p1 != null && p2 != null) {
			if (p1.equals(p2)) {
				return p1.val;
			}
			p1 = p1.parent;
			p2 = p2.parent;
		}
		return 0;
	}

	private void buildTree(TreeNode parent) {
		int val = preOrder[index++];
		if (val != 0) {
			TreeNode node = new TreeNode(val);
			records.put(val, node);
			node.parent = parent;
			buildTree(node);
			buildTree(node);
		}
	}

	private int getHeight(TreeNode p) {
		int height = 0;
		while (p != null) {
			++height;
			p = p.parent;
		}
		return height;
	}

	public static int[] str2IntArray(String line) {
		String[] strArray = line.split(" ");
		int n = strArray.length;
		int[] intArray = new int[n];
		for (int i = 0; i < n; ++i) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}

	public static void main(String[] args) {
		LowestCommonAncestor lca = new LowestCommonAncestor();
		Scanner reader = new Scanner(System.in);
		int n = reader.nextInt();
		reader.nextLine();
		for (int i = 0; i < n; ++i) {
			int[] preOrder = str2IntArray(reader.nextLine());
			int[] pq = str2IntArray(reader.nextLine());
			int p = pq[0];
			int q = pq[1];
			int ret = lca.lowestCommonAncestor(preOrder, p, q);
			System.out.println(ret == 0 ? "My God" : ret);
		}
		reader.close();
	}
}