http://www.lintcode.com/en/problem/lowest-common-ancestor-iii/

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes. The lowest common ancestor is the node with largest depth which is the ancestor of both nodes. Return null if LCA does not exist.

Example For the following binary tree:

    4
   / \
  3   7
     / \
    5   6

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

解题：LCA follow up，如果LCA不存在要返回null，我们就需要用一个数据结构来tracking 当前状态，ResultType是常用的方法，里面有a_exist, b_exist 两个属性，分别用来记录当前node有没有发现a，b。

class ResultType {
    public boolean a_exist, b_exist;
    public TreeNode node;
    ResultType(boolean a, boolean b, TreeNode n) {
        a_exist = a;
        b_exist = b;
        node = n;
    }
}

public class Solution {
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        ResultType re = helper(root, A, B);
        if (re.a_exist && re.b_exist) {
            return re.node;
        }
        return null;
    }
    public ResultType helper(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null)
            return new ResultType(false, false, null);

        //divide
        ResultType left_rt = helper(root.left, A, B);
        ResultType right_rt = helper(root.right, A, B);

        //conquer
        //check if A/B already found
        boolean a_exist = left_rt.a_exist || right_rt.a_exist || root == A;
        boolean b_exist = left_rt.b_exist || right_rt.b_exist || root == B;
        //find the node, we put the current node in result, no matter if it is the parent of another
        if (root == A || root == B)
            return new ResultType(a_exist, b_exist, root);
        //not the node, if left child and right child are not null, we find the ancestor
        if (left_rt.node != null && right_rt.node != null)
            return new ResultType(a_exist, b_exist, root);
        //not the node, if only left child is not null
        if (left_rt.node != null)
            return new ResultType(a_exist, b_exist, left_rt.node);
        //not the node, if only right child is not null
        if (right_rt.node != null)
            return new ResultType(a_exist, b_exist, right_rt.node);

        return new ResultType(a_exist, b_exist, null);
    }
}