给定n个叶子生成所有可能的二叉树

Question

因此，正如标题所暗示的那样，任何人都拥有/知道一种算法（如果可能的话，用java）来生成所有可能的二叉树，给定叶子的数量，如下面第二个链接的示例所示？

` N                  N                  N
 / \                / \                 /\
N   N               N  N               N  N
/\   /\             /\                     /\
N  N  N N           N  N                    N N
                   / \                        /\
                   N  N                       N N 

我已经去过 this 、 this 、 this 和 this 但我已经尝试过实现每一个，但它们没有做我正在寻找的事情或没有正确解释。如果我必须首先生成所有可能的字符串，然后将它们解析为树类型（父子关系），第一个将需要大量计算，而第二个不打印所有树。因为，例如，如果我像上面的示例一样通过指定 3 个内部节点来执行，它只会打印一棵树（左边的那棵）。我通过研究加泰罗尼亚数字知道，即使对于少量节点，树的数量也会增长很多，但对于少量节点来说是一个有用的工具。

Answer 1

我没有检查你的所有链接，但在我看来，其中一些链接有一些有用的想法。

回答你的问题，不，我不知道算法，但我不认为设计一个算法太难。

List<TreeNode> allBinaryTrees(int numberOfLeaves) {
    if (numberOfLeaves < 1) {
        throw new IllegalArgumentException("Number of leaves must be positive");
    }
    List<TreeNode> result = new ArrayList<>();
    if (numberOfLeaves == 1) {
        // return a single tree consisting of a single leaf node
        result.add(new Leaf());
        return result;
    }
    // We need one node for the root and at least one for the right subtree,
    // so the size of the left subtree
    // can only go up to numberOfLeaves - 2.
    for (int sizeOfLeftSubtree = 1; sizeOfLeftSubtree < numberOfLeaves - 1; sizeOfLeftSubtree++) {
        List<TreeNode> possibleLeftSubtrees = allBinaryTrees(sizeOfLeftSubtree);
        List<TreeNode> possibleRightSubtrees = allBinaryTrees(numberOfLeaves - sizeOfLeftSubtree);
        for (TreeNode lt : possibleLeftSubtrees) {
            for (TreeNode rt : possibleRightSubtrees) {
                // make a tree of a node with lt and rt as subtrees,
                // and add it to the result
                result.add(new InternalNode(lt, rt));
            }
        }
    }
    return result;
}

在上面我假设

InternalNode

和

Leaf

都是

TreeNode

的子类。您可能想要不同的设计。希望您能相应调整代码。