public void createAllTopologies(int n){
if(n%2 == 0) return;
Map<Integer, List<Node>> topologies = new HashMap<Integer, List<Node>>();
topologies.put(1, new ArrayList<Node>());
topologies.get(1).add(new Node(1));
for(int i=3;i<=n;i+=2){
List<Node> list = new ArrayList<Node>();
for(int j=1;j<i;j+=2){
List<Node> left = topologies.get(j);
List<Node> right = topologies.get(i-j-1);
list.addAll(generateAllCombinations(left,right));
}
topologies.put(i, list);
}
List<Node> result = topologies.get(n);
for(int i=0;i<result.size();i++){
printTree(result.get(i),0);
System.out.println("-----------------------------");
}
}
private List<Node> generateAllCombinations(List<Node> left, List<Node> right) {
List<Node> list = new ArrayList<Node>();
for(int i=0;i<left.size();i++){
for(int j=0;j<right.size();j++){
Node nNode = new Node(1);
nNode.left = left.get(i).clone();
nNode.right = right.get(j).clone();
list.add(nNode);
}
}
return list;
}
/* This prints tree from left to right fashion i.e
root at left,
leftNode at bottom,
rightNode at top
*/
protected void printTree(Node nNode,int pos){
if (nNode==null) {
for(int i=0;i<pos;i++) System.out.print("\t");
System.out.println("*");
return;
}
printTree(nNode.right,pos+1);
for(int i=0;i<pos;i++) System.out.print("\t");
System.out.println(nNode.data);
printTree(nNode.left,pos+1);
}
我在这里使用递归。通过使用动态规划,可以改进此代码。希望这有所帮助。我们从左侧开始一个节点,一个节点作为根节点,右侧有N-i-1个节点。然后,我们将节点成对从右侧移动到左侧。
import java.util.ArrayList;
import java.util.List;
public class NumberOfFullBTrees {
public static void main(String[] args) {
int N = 5;
NumberOfFullBTrees numberOfFullBTrees = new NumberOfFullBTrees();
List<TreeNode> result = numberOfFullBTrees.allPossibleFBT(N);
}
/**
* Builds all possible full binary trees. We start by 1 node in left, 1 note at root and n-2 node in right.
* We move the nodes in pairs from right to left. This method uses recursion. This method can be improved by
* using dynamic programming.
*
* @param N The number of nodes
* @return The possible full binary trees with N nodes as a list
*/
public List<TreeNode> allPossibleFBT(int N) {
List<TreeNode> result = new ArrayList<>();
if (N % 2 == 0) {
return result;
}
if (N == 1) {
result.add(new TreeNode(0));
return result;
}
for (int i = 1; i < N; i += 2) {
List<TreeNode> lefts = allPossibleFBT(i);
List<TreeNode> rights = allPossibleFBT(N - i - 1);
for (TreeNode l : lefts) {
for (TreeNode r : rights) {
TreeNode root = new TreeNode(0);
root.left = l;
root.right = r;
result.add(root);
}
}
}
return result;
}
}