二叉樹的遞回套路——最低公共祖先

給定一棵二叉樹的頭節點head,和另外兩個節點a和b，回傳a和b的最低公共祖先（a和b有可能不在這棵樹上）

最低公共祖先：a和b往上走初次交匯的點

方法一

不用二叉樹的遞回套路：準備一張HashMap和HashSet，在遍歷整棵樹的時候，HashMap用來存放每個結點和父結點，a結點一直往父結點方向走，沿途全部加入HashSet，然后b結點往上走的程序，第一個在HashSet里的就是兩個結點的最低公共祖先， 這個方法缺點很明顯，雖然時間復雜度仍然是O(N)，但是不夠簡潔，不僅跑了個遞回，而且還填滿了一張表，之后還要從指定結點往上回溯，沿途結點加入HashSet，然后用另外一個結點來回溯比較，太麻煩啦！！！

方法二

二叉樹的遞回套路：按照慣例，我們來列可能性（假設以X為頭節點的整棵樹）

1）a和b都不在以X為頭結點的整棵樹上
2）a和b只有一個在以X為頭結點的整棵樹上
3）a和b都在以x為頭結點的樹上（又有四種情況）
1》左樹右樹各一個
2》左樹有兩個
3》右樹有兩個
4》x自己是a或b

整合一下，任何子樹需要回傳資訊就是：

public static class Info{
		// a和b最初交匯點，沒有交匯點回傳null
		public Node ans;
		// 在子樹上是否發現a
		public boolean findA;
		// 在子樹上是否發現b
		public boolean findB;
		
		public Info(Node n,boolean fa,boolean fb) {
			ans=n;
			findA=fa;
			findB=fb;
		}
}

完整代碼：

package com.harrison.class08;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Code09_LowestAncestor {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node lowestAncestor1(Node head, Node a, Node b) {
		if (head == null) {
			return null;
		}
		HashMap<Node, Node> parentMap = new HashMap<>();
		parentMap.put(head, null);
		fillParentMap(head, parentMap);
		HashSet<Node> aSet = new HashSet<>();
		Node cur = a;
		aSet.add(cur);
		while (parentMap.get(cur) != null) {
			cur = parentMap.get(cur);
			aSet.add(cur);
		}
		cur = b;
		while (!aSet.contains(cur)) {
			cur = parentMap.get(cur);
		}
		return cur;
	}

	public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
		if (head.left != null) {
			parentMap.put(head.left, head);
			fillParentMap(head.left, parentMap);
		}
		if (head.right != null) {
			parentMap.put(head.right, head);
			fillParentMap(head.right, parentMap);
		}
	}

	public static class Info {
		// a和b最初交匯點，沒有交匯點回傳null
		public Node ans;
		// 在子樹上是否發現a
		public boolean findA;
		// 在子樹上是否發現b
		public boolean findB;

		public Info(Node n, boolean fa, boolean fb) {
			ans = n;
			findA = fa;
			findB = fb;
		}
	}

	public static Info process1(Node head, Node a, Node b) {
		if (head == null) {
			return new Info(null, false, false);
		}
		Info leftInfo = process1(head.left, a, b);
		Info rightInfo = process1(head.right, a, b);
		// 如何算是發現這個結點，要么頭節點是，要么左樹上有，要么右樹上有
		boolean findA = (head == a || leftInfo.findA || rightInfo.findA);
		boolean findB = (head == b || leftInfo.findB || rightInfo.findB);
		// 先假設a,b沒有交匯點
		// a和b的交匯點在哪？
		// 左樹上提前交會 || 右樹上提前交會 || 兩邊都沒有提前交會，那就是頭節點處交會
		Node ans = null;
		if (leftInfo.ans != null) {
			ans = leftInfo.ans;
		}
		if (rightInfo.ans != null) {
			ans = rightInfo.ans;
		}
		if (ans == null) {
			if (findA && findB) {
				ans = head;
			}
		}
		return new Info(ans, findA, findB);
	}

	public static Node lowestAncestor2(Node head, Node a, Node b) {
		return process1(head, a, b).ans;
	}

	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static Node pickRandomOne(Node head) {
		if (head == null) {
			return null;
		}
		ArrayList<Node> arr = new ArrayList<>();
		fillPreList(head, arr);
		int randomIndex = (int) (Math.random() * arr.size());
		return arr.get(randomIndex);
	}

	public static void fillPreList(Node head, ArrayList<Node> arr) {
		if (head == null) {
			return;
		}
		arr.add(head);
		fillPreList(head.left, arr);
		fillPreList(head.right, arr);
	}

	public static void main(String[] args) {
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			Node o1 = pickRandomOne(head);
			Node o2 = pickRandomOne(head);
			if (lowestAncestor1(head, o1, o2) != lowestAncestor2(head, o1, o2)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}
}