forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
AllPossibleFullBinaryTrees.java
161 lines (149 loc) · 4.93 KB
/
AllPossibleFullBinaryTrees.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
/*https://leetcode.com/problems/all-possible-full-binary-trees/*/
class Solution {
StringBuffer key;
int count, n;
List<TreeNode> list;
TreeNode cloneTree;
HashMap<String,Integer> map;
public List<TreeNode> allPossibleFBT(int n) {
if (n%2 == 0) return new ArrayList<TreeNode>(); //even number of nodes is not possible
map = new HashMap<String,Integer>(); //create a map for dp
this.n = n; //store n globally
TreeNode root = new TreeNode(0); //create a root node
list = new ArrayList<TreeNode>(); //create a list of nodes
recurTreeGenerator(root,1); //recursion call
return list;
}
public void recurTreeGenerator(TreeNode root, int currTreeSize)
{
String treeKey = generateTreeKey(root); //get the key of current tree
if (map.containsKey(treeKey)) return; //if key is already checked, return
if (currTreeSize == n) //if current tree size is n
{
cloneTree = new TreeNode(0); //create a new node
clone(root,cloneTree); //clone the current tree
list.add(cloneTree); //add to list
map.put(treeKey,1); //add to dp
return;
}
map.put(treeKey,1); //add to dp
Stack<TreeNode> stack = new Stack<TreeNode>(); //create a stack
//push root to stack
stack.push(root);
while (!stack.isEmpty())
{
//pop from stack and add to the list
TreeNode temp = stack.pop();
if (temp.left == null && temp.right == null) //if current node is a leaf
{
//attach two children
temp.left = new TreeNode(0);
temp.right = new TreeNode(0);
/*recursion call*/
recurTreeGenerator(root, currTreeSize+2);
//backtracking
temp.left = null;
temp.right = null;
}
//add its children, first right then left
if (temp.right != null)
stack.push(temp.right);
if (temp.left != null)
stack.push(temp.left);
}
}
public void clone(TreeNode root, TreeNode copy)
{
if (root.left != null) //if left child is present
{
copy.left = new TreeNode(0); //create a left child in clone tree
clone(root.left,copy.left); //recur on left child
}
if (root.right != null) //if right child is present
{
copy.right = new TreeNode(0); //create a right child in clone tree
clone(root.right,copy.right); //recur on right child
}
}
public String generateTreeKey(TreeNode root)
{
key = new StringBuffer("#");
recurKeyGenerator(root);
return key.toString();
}
public void recurKeyGenerator(TreeNode root)
{
if (root == null) //if root is null
{
key.append("0"); //append 0
key.append("#");
return;
}
key.append("1"); //append 1
key.append("#");
recurKeyGenerator(root.left); //recur on left child
recurKeyGenerator(root.right); //recur on right child
}
}
class Solution {
private List<TreeNode>[] dp;
public List<TreeNode> allPossibleFBT(int n) {
if (n % 2 == 0) {
return new LinkedList<>();
}
dp = new LinkedList[n+1];
return buildTree(n);
}
private List<TreeNode> buildTree(int n) {
List<TreeNode> list = new LinkedList<>();
if (n <= 0) {
return list;
}
if (n == 1) {
TreeNode root = new TreeNode(0);
list.add(root);
return list;
}
if (dp[n] != null) {
return dp[n];
}
for (int i = 1; i < n; i += 2) {
int j = n - i - 1;
List<TreeNode> left = buildTree(i);
List<TreeNode> right = buildTree(j);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(0);
root.left = l;
root.right = r;
list.add(root);
}
}
}
dp[n] = list;
return list;
}
}
class Solution {
public List<TreeNode> allPossibleFBT(int N) {
List<TreeNode> res = new ArrayList<>();
if(N==1){
res.add(new TreeNode(0));
return res;
}
N=N-1;
for(int i=1; i<N;i+=2){
List<TreeNode> left = allPossibleFBT(i);
List<TreeNode> right = allPossibleFBT(N-i);
for(TreeNode nl: left){
for(TreeNode nr:right){
TreeNode cur = new TreeNode(0);
cur.left=nl;
cur.right=nr;
res.add(cur);
}
}
}
return res;
}
}