CC4.7.java

    public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (!isExisted(root, p) || !isExisted(root, q))
            return null;
        return LCA_helper(root, p, q);
    }
    
    private boolean isExisted(TreeNode root, TreeNode node) {
        if (root == null)
            return false;
        if (root == node)
            return true;
        return isExisted(root, node.left) || isExisted(root, node.right);
    }

    private TreeNode LCA_helper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (root == p || root == q)
            return root;
        // only look at left side
        boolean ponleft = isExisted(root.left, p);
        boolean qonleft = isExisted(root.left, q);
        if (ponleft != qonleft)
            return root;
        else if (ponleft)
            return LCA_helper(root.left, p, q);
        else 
            return LCA_helper(root.right, p, q);
    }