在二叉树中找到两个节点的最近公共祖先

import java.util.*;
//在二叉树中找到两个节点的最近公共祖先
public class GetLowestTree{
	//二叉树节点的定义
	public static class Node{

		public int value;

		public Node left;

		public Node right;

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

	//找到两个节点的最近公共祖先
	public static Node GetLowestAncestor(Node head,Node n1,Node n2)
	{   
		//递归的出口
		if(head==null||n1==head||n2==head)
		{
			return head;
		}
         //递归调用
		Node left=GetLowestAncestor(head.left,n1,n2);  //左子树
		Node right=GetLowestAncestor(head.right,n1,n2); //右子树
		if(left!=null&&right!=null)
		{
			return head;
		}
		return left!=null?left:right;

	}

//***************************************************
   // 直观打印二叉树
	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + head.value + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
	}
//***************************************************
  // 进阶问题--方法一(构造hash表)
	public static class Record1 {
		private HashMap<Node, Node> map;

		public Record1(Node head) {
			map = new HashMap<Node, Node>();
			if (head != null) {
				map.put(head, null);
			}
			setMap(head);
		}

		private void setMap(Node head) {
			if (head == null) {
				return;
			}
			if (head.left != null) {
				map.put(head.left, head);
			}
			if (head.right != null) {
				map.put(head.right, head);
			}
			setMap(head.left);
			setMap(head.right);
		}

		public Node query(Node o1, Node o2) {
			HashSet<Node> path = new HashSet<Node>();
			while (map.containsKey(o1)) {
				path.add(o1);
				o1 = map.get(o1);
			}
			while (!path.contains(o2)) {
				o2 = map.get(o2);
			}
			return o2;
		}

	}

	// 进阶问题--方法二
	public static class Record2 {
		private HashMap<Node, HashMap<Node, Node>> map;

		public Record2(Node head) {
			map = new HashMap<Node, HashMap<Node, Node>>();
			initMap(head);
			setMap(head);
		}

		private void initMap(Node head) {
			if (head == null) {
				return;
			}
			map.put(head, new HashMap<Node, Node>());
			initMap(head.left);
			initMap(head.right);
		}

		private void setMap(Node head) {
			if (head == null) {
				return;
			}
			headRecord(head.left, head);
			headRecord(head.right, head);
			subRecord(head);
			setMap(head.left);
			setMap(head.right);
		}

		private void headRecord(Node n, Node h) {
			if (n == null) {
				return;
			}
			map.get(n).put(h, h);
			headRecord(n.left, h);
			headRecord(n.right, h);
		}

		private void subRecord(Node head) {
			if (head == null) {
				return;
			}
			preLeft(head.left, head.right, head);
			subRecord(head.left);
			subRecord(head.right);
		}

		private void preLeft(Node l, Node r, Node h) {
			if (l == null) {
				return;
			}
			preRight(l, r, h);
			preLeft(l.left, r, h);
			preLeft(l.right, r, h);
		}

		private void preRight(Node l, Node r, Node h) {
			if (r == null) {
				return;
			}
			map.get(l).put(r, h);
			preRight(l, r.left, h);
			preRight(l, r.right, h);
		}

		public Node query(Node o1, Node o2) {
			if (o1 == o2) {
				return o1;
			}
			if (map.containsKey(o1)) {
				return map.get(o1).get(o2);
			}
			if (map.containsKey(o2)) {
				return map.get(o2).get(o1);
			}
			return null;
		}

	}
	public static void main(String[]args)
	{
		//System.out.println("Hello");
		Node head=new Node(1);
		head.left=new Node(2);
		head.right=new Node(3);
		head.left.left=new Node(4);
		head.left.right=new Node(5);
		head.right.left=new Node(6);
		head.right.right=new Node(7);
		head.right.right.left=new Node(8);
    
        printTree(head);
        Node node=GetLowestAncestor(head,head.left,head.right);
		System.out.println(node.value);


        Node o1 = head.left.right;
		Node o2 = head.right.left;
		// 生成map后方便多次查询--进阶问题
		Record1 record1 = new Record1(head);
		Record2 record2 = new Record2(head);

		System.out.println("o1 : " + o1.value);
		System.out.println("o2 : " + o2.value);
		System.out.println("ancestor : " + record1.query(o1, o2).value);
		System.out.println("ancestor : " + record2.query(o1, o2).value);

		o1 = head.left.left;
		o2 = head.left;
		System.out.println("o1 : " + o1.value);
		System.out.println("o2 : " + o2.value);
		System.out.println("ancestor : " + record1.query(o1, o2).value);
		System.out.println("ancestor : " + record2.query(o1, o2).value);

		o1 = head.right.left;
		o2 = head.right.right.left;
		System.out.println("o1 : " + o1.value);
		System.out.println("o2 : " + o2.value);
		System.out.println("ancestor : " + record1.query(o1, o2).value);
		System.out.println("ancestor : " + record2.query(o1, o2).value);

	}
		
}