Lowest Common Ancestor III

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.

Returnnullif LCA does not exist.

这个题目使用devide and conque

关键点：

1，构造一个class，使用ResultType作为 recusion的 返回变量

 里面要construct  bollean  a，b是否存在，还要包括 root的node本身

2， 考虑如果 A或B node根本在二叉树里不存在

3， A和B 在某单调子二叉树里

     public class Solution {
    /**
     * @param root The root of the binary tree.
     * @param A and B two nodes
     * @return: Return the LCA of the two nodes.
     */
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here

        ResultType result = helper(root,A,B);
        if(result.a_exist && result.b_exist){
            return result.node;
        }

        return null;
    }

    private ResultType helper(TreeNode root, TreeNode A, TreeNode B){
        if(root == null){
            return new ResultType(false,false,root);
        }

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

        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;

        if(root == A || root ==B){
            return new ResultType(a_exist,b_exist,root);
        }

        if (left_rt.node != null && right_rt.node != null){
            return new ResultType(a_exist,b_exist,root);
        }

        if (left_rt.node != null){
            return new ResultType(a_exist,b_exist,left_rt.node);
        }

        if(right_rt.node != null){
            return new ResultType(a_exist,b_exist,right_rt.node);
        }

       return new ResultType(a_exist, b_exist, null);

    }
}    

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;
    }
}