输入：4，5。输出：2。

输入：4，9。输出：1.

从root开始遍历，如果n1和n2中的任一个和root匹配，那么root就是LCA。 如果都不匹配，则分别递归左、右子树，如果有一个 key（n1或n2）出现在左子树，并且另一个key(n1或n2)出现在右子树，则root就是LCA.  如果两个key都出现在左子树，则说明LCA在左子树中，否则在右子树。

public class Test16 {
    static class Node {
        int val;
        Node left, right;

        public Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static Node findLowestCommonAncestor(Node head, int n1, int n2) {
        if (head == null) {
            return null;
        }
        if (head.val == n1 || head.val == n2) {
            return head;
        }
        Node leftFind = findLowestCommonAncestor(head.left, n1, n2);
        Node rightFind = findLowestCommonAncestor(head.right, n1, n2);
        if (leftFind != null && rightFind != null) {
            return head;
        }
        if (leftFind != null) {
            return leftFind;
        }
        if (rightFind != null) {
            return rightFind;
        }
        return null;
    }

    public static void main(String[] args) {
        Node n10 = new Node(10, null, null);
        Node n9 = new Node(9, null, null);
        Node n8 = new Node(8, null, null);
        Node n7 = new Node(7, null, null);
        Node n5 = new Node(5, null, null);
        Node n6 = new Node(6, n9, n10);
        Node n4 = new Node(4, n7, n8);
        Node n3 = new Node(3, null, n6);
        Node n2 = new Node(2, n4, n5);
        Node n1 = new Node(1, n2, n3);

        System.out.println(findLowestCommonAncestor(n1,4,9).val);
    }
}