一个用Java写的关于完全二叉树的问题

我想写一个程序，由用户输入树的叶子节点的个数。程序输出满足条件（该完全二叉树中的叶子节点的个数为用户输入的数值）的二叉树的结构或者表达式。比如根节点用R表示，内部节点用K表示，叶子节点用M表示。
例如：
2个叶子节点的树为：(MAM)
3个叶子节点的树为:(MA(MKM))  ((MKM)AM)
之前有两个思路：
1个是：在2个叶子节点的数的基础上，添加节点，直到满足个数为止
2是：通过递归，比如4个节点的树可以分为三种
      左节点和有几点分别为1 3,2 2,3 1
      再对其中子节点的节点进行递归构造
我用了第二种方法写程序，思路有点乱。希望诸位帮帮忙。感激不尽！！！