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

note that the node A or B doesn't guarantee existence. so we need to discuss different scenario.we need a return type with two boolean to remember whether both of the nodes exists

1. root == A || root == B
2. one on each side
3. only one on left
4. only one on right

pre-calculate the two boolean for that iteration and use the value in the return

class ReturnType {
        TreeNode root;
        boolean hasA;
        boolean hasB;

        public ReturnType(TreeNode root, boolean hasA, boolean hasB) {
            this.root = root;
            this.hasA = hasA;
            this.hasB = hasB;
        }
    }

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if (root == null) {
            return null;
        }

        ReturnType ans = lcaHelper(root, A, B);
        if (ans.hasA && ans.hasB) {
            return ans.root;
        }

        return null;



    }


    public ReturnType lcaHelper(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null) {
            return new ReturnType(null, false, false);
        }

        ReturnType left = lcaHelper(root.left, A, B);
        ReturnType right = lcaHelper(root.right, A, B);

        boolean aExist = left.hasA || right.hasA || root == A;
        boolean bExist = left.hasB || right.hasB || root == B;

        if (root == A || root == B) {
            return new ReturnType(root, aExist, bExist);
        }

        if (left.root != null && right.root != null) {
            return new ReturnType(root, aExist, bExist);
        }

        if (left.root != null) {
            return new ReturnType(left.root, aExist, bExist);
        }

        if (right.root != null) {
            return new ReturnType(right.root, aExist, bExist);
        }

        return new ReturnType(null, false, false);


    }