I don’t get why we are adding the root of every sub-tree in the result.
public static List<TreeNode> findUniqueTrees(int n) {
if (n <= 0)
return new ArrayList<TreeNode>();
return findUniqueTreesRecursive(1, n);
}
public static List<TreeNode> findUniqueTreesRecursive(int start, int end) {
List<TreeNode> result = new ArrayList<>();
if (start > end) {
result.add(null);
return result;
}
for (int i = start; i <= end; i++) {
// making 'i' root of the tree
List<TreeNode> leftSubtrees = findUniqueTreesRecursive(start, i - 1);
List<TreeNode> rightSubtrees = findUniqueTreesRecursive(i + 1, end);
for (TreeNode leftTree : leftSubtrees) {
for (TreeNode rightTree : rightSubtrees) {
TreeNode root = new TreeNode(i);
root.left = leftTree;
root.right = rightTree;
result.add(root); **// Why is this line required for all the sub cases?**
}
}
}
return result;
}