solutions such as
is accepted by OJ. However, I find a problem with it. The structure of the tree is bad. It uses multiply root nodes of different trees pointing to the same substree object. So if we modify one of the trees of output list, the other trees will be affected. We need a deep copy of every tree node. Different trees cannot share common components. That's why I use a cloneTree() to deep copy every node instead of just pointing to the same subtree component.
public class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) { return new ArrayList<>(); } return generateTreesHelper(1, n); } private List<TreeNode> generateTreesHelper(int start, int end) { List<TreeNode> uniqueTrees = new ArrayList<>(); if (start > end) { uniqueTrees.add(null); return uniqueTrees; } TreeNode root; List<TreeNode> leftSubtrees, rightSubtrees; for (int i = start; i <= end; i++) { leftSubtrees = generateTreesHelper(start, i - 1); rightSubtrees = generateTreesHelper(i + 1, end); for (TreeNode leftSubtree : leftSubtrees) { for (TreeNode rightSubtree : rightSubtrees) { root = new TreeNode(i); root.left = cloneTree(leftSubtree); // must make a copy root.right = cloneTree(rightSubtree); // for each different tree uniqueTrees.add(root); } } } return uniqueTrees; } private TreeNode cloneTree(TreeNode root) { if (root == null) { return null; } TreeNode newRoot = new TreeNode(root.val); newRoot.left = cloneTree(root.left); newRoot.right = cloneTree(root.right); return newRoot; } }
your understanding is incorrect. If you don't believe that, you can play in the local IDE and see. (The original post is correct, see discussion below.)
Think about this: if every root node is brand new, how about the roots of the subtrees?
You see the double loop there? That is where you start reusing the subtrees.
For different root new just created, you reuse the left subtree in the loop.
I know you mean the recursion. But actually there is no recursion for the subtrees. They have been already placed in the list. All you did is pointing different roots to the same subtrees
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.