二叉樹中找到兩個節點的最近公共祖先

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

/**
 * Created by lxw, [email protected] on 2017/10/30.
 * 二叉樹中找到兩個節點的最近公共祖先
 */
public class CommonAncestor {

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

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

    public Node lowestAncestor(Node head, Node n1, Node n2){
        if(head == null || head == n1 || head == n2){
            return head;
        }
        Node left = lowestAncestor(head.left, n1, n2);
        Node right = lowestAncestor(head.right, n1, n2);
        if(left != null && right != null){
            return head;
        }
        return left != null ? left : right;
    }

    public class Record{
        private HashMap<Node, Node> map = new HashMap<Node, Node>();
        public Record(Node head){
            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 n1, Node n2){
            HashSet<Node> set = new HashSet<Node>();
            while (map.containsKey(n1)){
                set.add(n1);
                n1 = map.get(n1);
            }
            while (!set.contains(n2)){
                n2 = map.get(n2);
            }
        }

    }
}